51Nod--1002 数塔取数问题

r囧r小猫 2022-06-15 10:52 150阅读 0赞

因为5-31晚停电，所以6-1补上

题目链接：[http://www.51nod.com/onlineJudge/questionCode.html\#!problemId=1002][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;
    }

[http_www.51nod.com_onlineJudge_questionCode.html_problemId_1002]: http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1002