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