Wikioi

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
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);

}

}

运行结果为:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
please input the height:
5
please input datas:

7
3
8
8
1
0
2
7
4
4
4
5
2
6
5
25

作者:有奶喝先森
链接:http://www.jianshu.com/p/29707d65f420
來源:简书
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。