动态规划-走方格

/*
一个NN矩阵中有不同的正整数,经过这个格子,就能获得相应价值的奖励,从左上走到右下,
只能向下向右走,求能够获得的最大价值。例如:3
3的方格。

1 3 3
2 1 3
2 2 1

能够获得的最大价值为:11

输入 n
3
1 3 3
2 1 3
2 2 1
输出11

3
1 3 3
2 10 1
2 2 1
输出17
*/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
package dp;

import java.util.Scanner;
public class JuZhenQuShu {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = Integer.parseInt(in.nextLine())+1;
int[][] dp = new int[n][n];

for (int i = 1; i < n; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = in.nextInt();
}
}

for (int i = 1; i < n; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = Math.max(dp[i-1][j]+dp[i][j],dp[i][j]+dp[i][j-1]);
}
}

System.out.println(dp[n-1][n-1]);



}
}