dp[i][j]表示到达arr[i][j]时的最大路径:
- dp[0][0] = arr[0][0]
- 当 j = 0时,即最左侧,只能由正上方到达, dp[i][0] = dp[i-1][0] + arr[i][0]
- 当 j = k-1, i = k-1 (第k行,第k列)时,只能由左上方到达, dp[i][j] = dp[i-1][j-1] + dp[i][j]
- 当 j > 0时,能由左上方或者正上方到达, dp[i][j] = min( dp[i-1][j-1], dp[i-1][j] ) + arr[j][0]
- 选择j = n-1时的最大值
由于每次操作不重复,可以在arr的基础上直接进行操作,不需要再构造新的dp
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = Integer.parseInt(scanner.nextLine());
if(n == 0){
System.out.println(0);
return;
}
List<List<Integer>> arr = new ArrayList<>();
//读取数据
for (int i = 0; i < n; i++) {
String[] line = scanner.nextLine().split(" ");
List<Integer> list = new ArrayList<>();
for (String item: line) {
list.add(Integer.parseInt(item));
}
arr.add(list);
}
//最左侧
for (int i = 1; i < n; i++) {
arr.get(i).set(0, arr.get(i-1).get(0) + arr.get(i).get(0));
}
//最右侧
for (int i = 1; i < n; i++) {
arr.get(i).set(i, arr.get(i-1).get(i-1) + arr.get(i).get(i));
}
//其余部分, i >= 2, 1<= j < i
for (int i = 2; i < n; i++) {
for (int j = 1; j < i; j++) {
arr.get(i).set(j,
Math.max( arr.get(i-1).get(j-1), arr.get(i-1).get(j) ) + arr.get(i).get(j) );
}
}
int sum = 0;
//找到最大值并返回
for (int j = 0; j < n ; j++) {
sum = Math.max(sum, arr.get(n-1).get(j));
}
System.out.println(sum);
}
}