题目链接:http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1002
一个高度为N的由正整数组成的三角形,从上走到下,求经过的数字和的最大值。 每次只能走到下一层相邻的数上,例如从第3层的6向下走,只能走到第4层的2或9上。
5 8 4 3 6 9 7 2 9 5
例子中的最优方案是:5 + 8 + 6 + 9 = 28 Input 第1行:N,N为数塔的高度。(2 <= N <= 500) 第2 - N + 1行:每行包括1层数塔的数字,第2行1个数,第3行2个数……第k+1行k个数。数与数之间用空格分隔(0 <= A[i] <= 10^5) 。 Output 输出最大值 Input示例 4 5 8 4 3 6 9 7 2 9 5 Output示例 28
本题一开始可能会想到直接DFS 搜索,但是这样时间复杂度偏高。一个聪明一点的想法是利用动态规划的思想,从最后一层开始向上,因为每次有两种路径选择(直下方数字和斜下方数字),那么每次取得这两种情况中数字较大的那种情况… 一直到第一层,就是答案。代码:
#include <iostream>
using namespace std;
int a[510][510];
int res[510];
int main() {
int n;
cin >> n;
for(int i = 0; i < n; i++) {
for(int j = 0; j <= i; j++) {
scanf("%d", a[i]+j);
// 将res数组赋值为最底层数字
if(i == n-1) {
res[j] = a[i][j];
}
}
}
// 从倒数第二层开始一直到第一层:
for(int i = n-2; i >= 0; i--) {
for(int j = 0; j <= i; j++) {
// 取得两种路径中较大的数字的那一种情况。
res[j] = max(a[i][j]+res[j], a[i][j]+res[j+1]);
}
}
// 到最后第一层的数字就是答案
cout << res[0] << endl;
return 0;
}