Wikioi
package new2017;
import java.util.Scanner;
public class Wikioi {
public static void main(String[] args) {
// 数组构建
Scanner scan = new Scanner(System.in);
System.out.println("please input the height:");
int n = scan.nextInt();
int[][] a = new int[n][];
for (int i = 0; i < n; i++) {
a[i] = new int[i + 1];
}
System.out.println("please input datas:");
for (int i = 0; i < n; i++) {
for (int j = 0; j <= i; j++) {
a[i][j] = scan.nextInt();
}
}
// int[][] a = { { 7 }, { 3, 8 }, { 8, 1, 0 }, { 2, 7, 4, 4 }, { 4, 5, 2, 6, 5 } };
// int n = a.length;
int[][] dp = new int[n][n];
int ans = 0x80000000;// -2147483648
for (int i = 0; i < n; i++) {
for (int j = 0; j <= i; j++) {
if (i == 0) {// 第一层
dp[0][0] = a[0][0];
} else {
if (j == 0) {// 每一层的最左边单独处理
dp[i][j] = dp[i - 1][0] + a[i][j];
} else if (j == i) {// 每一层的最右边单独处理
dp[i][j] = dp[i - 1][i - 1] + a[i][j];
} else {// 中间的比较对应的上面两个哪个大
dp[i][j] = dp[i - 1][j - 1] > dp[i - 1][j] ? dp[i - 1][j - 1] : dp[i - 1][j] + a[i][j];
}
}
}
}
for (int j = 0; j < n; j++) {// 遍历最后一层
if (dp[n - 1][j] > ans) {
ans = dp[n - 1][j];
}
}
System.out.println(ans);
}
}
运行结果为：
please input the height:
5
please input datas:7
3
8
8
1
0
2
7
4
4
4
5
2
6
5
25
