首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >51Nod--1002 数塔取数问题

51Nod--1002 数塔取数问题

作者头像
指点
发布2019-01-18 15:27:54
5130
发布2019-01-18 15:27:54
举报
文章被收录于专栏:指点的专栏指点的专栏

题目链接: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;
} 
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2017年06月01日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档