dp和dfs两种解法（java）

参考代码:

import java.util.*;

public class Main {

static int n;

static int[][]g=new int[26][26];

static int[][]dp=new int[26][26];

static int[]dx= {1,1};

static int[]dy= {1,0};

static int max=0;

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

n=sc.nextInt();

for(int i=1;i<=n;i++) {

    for(int j=1;j<=i;j++) {

    g[i][j]=sc.nextInt();

    }

}

//dfs(1,1,g[1][1]);

dp[1][1]=g[1][1];

for(int i=1;i<=n;i++) {

    for(int j=1;j<=n;j++) {

    dp[i][j]=Math.max(dp[i-1][j-1]+g[i][j], dp[i-1][j]+g[i][j]);

    }

}

for( int i=1;i<=n;i++) {

    max=Math.max(max,dp[n][i]);

}

System.out.print(max);

}

public static void dfs(int x,int y,int sum) {

    if(x<1||x>n||y<1||y>n)return;

    if(x==n) {

    max=Math.max(max, sum);

    return;

    }

    for(int i=0;i<2;i++) {

    int a=x+dx[i];

    int b=y+dy[i];

    if(a<1||a>n||b<1||b>n)continue;

    dfs(a,b,sum+g[a][b]);

    }

}

}