51Nod--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;
} 

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券