51nod 1002数塔取数 dp

不念不忘少年蓝@ 2022-08-20 13:11 193阅读 0赞

一个高度为N的由正整数组成的三角形，从上走到下，求经过的数字和的最大值。

每次只能走到下一层相邻的数上，例如从第3层的6向下走，只能走到第4层的2或9上。

5

8 4

3 6 9

7 2 9 5

例子中的最优方案是：5 + 8 + 6 + 9 = 28

一道比较简单的dp问题。

dp\[i\]\[j\]表示的是从位置(1,1)到位置(i,j)的最优方案.递推公式为dp\[i\]\[j\] = max(dp\[i-1\]\[j-1\],dp\[i-1\]\[j\]) + a\[i\]\[j\] ;

最后扫描一遍最下方的位置取最大值就可以了。

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <algorithm>
    using namespace std;
    
    int const maxn = 505;
    int a[maxn][maxn];
    int dp[maxn][maxn];
    //dp[i][j]从位置（1,1）走到位置(i,j)得到的价值
    
    int main()
    {
        int n;
        while(scanf("%d",&n)!=EOF)
        {
            for(int i = 1 ; i <= n ; i++)
            {
                for(int j = 1 ; j <= i ; j++)
                {
                    scanf("%d",&a[i][j]);
                }
            }
            memset(dp,0,sizeof(dp));
            for(int i = 1 ; i <= n ; i++)
            {
                for(int j = 1 ; j <= i ; j++)
                {
                    dp[i][j] = max(dp[i-1][j-1],dp[i-1][j])+a[i][j];
                }
            }
            int ans = dp[n][1] ;
            for(int i = 1 ; i <= n ; i++)
            {
                ans = max(ans,dp[n][i]);
            }
            printf("%d\n",ans);
        }
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，193人围观）

还没有评论，来说两句吧...

相关阅读

相关 51nod1230 幸运数 (数位dp）

[1230 幸运数][1230] ![ok.png][] 题目来源： [HackerRank][] [1230]: http://www.51nod.com/o

柔光的暖阳◎/ 2024年02月18日 18:31/ 0 赞/ 49 阅读

相关 51nod 1717 好数

有n个数 a\[1\],a\[2\],...,a\[n\]开始都是0 现在进行操作 t从1~n依次增加每次把下标时t的倍数的数都反转（0变成1,1变成0）如果最后a\

灰太狼/ 2024年02月17日 22:49/ 0 赞/ 19 阅读

相关 51nod 1084 矩阵取数问题 V2 dp

[1084 矩阵取数问题][1084] V2 基准时间限制：2 秒空间限制：131072 KB 分值: 80 [难度：5级算法题][5] 收藏关注一个M\N矩阵中

心已赠人/ 2024年02月17日 19:19/ 0 赞/ 89 阅读

相关 51nod 1002数塔取数 dp

一个高度为N的由正整数组成的三角形，从上走到下，求经过的数字和的最大值。每次只能走到下一层相邻的数上，例如从第3层的6向下走，只能走到第4层的2或9上。

不念不忘少年蓝@/ 2022年08月20日 13:11/ 0 赞/ 194 阅读

相关 51nod 1084+1083 矩阵取数问题 dp

先来说这个比较简单的问题：一个N\N矩阵中有不同的正整数，经过这个格子，就能获得相应价值的奖励，从左上走到右下，只能向下向右走，求能够获得的最大价值。例如：3 \ 3的

刺骨的言语ヽ痛彻心扉/ 2022年08月20日 12:26/ 0 赞/ 62 阅读

相关 51Nod--1002 数塔取数问题

因为5-31晚停电，所以6-1补上题目链接：[http://www.51nod.com/onlineJudge/questionCode.html\!problemId=1

r囧r小猫/ 2022年06月15日 10:52/ 0 赞/ 228 阅读

相关 51nod 1083 矩阵取数问题

[1083 矩阵取数问题][1083] ![ok.png][] 基准时间限制：1 秒空间限制：131072 KB 分值: 5 [难度：1级算法题][1] ![star.p

浅浅的花香味﹌/ 2022年06月15日 04:15/ 0 赞/ 192 阅读

相关 51Nod--1015 水仙花数

题目链接：[http://www.51nod.com/onlineJudge/questionCode.html\!problemId=1015][http_www.51nod

小鱼儿/ 2022年06月14日 08:30/ 0 赞/ 211 阅读

相关数塔——DP算法

在讲述DP算法的时候，一个经典的例子就是数塔问题，它是这样描述的：有如下所示的数塔，要求从顶层走到底层，若每一步只能走到相邻的结点，则经过的结点的数字之和最大是多少？

古城微笑少年丶/ 2022年06月12日 01:41/ 0 赞/ 267 阅读

相关 HDU2084：数塔(DP)

Problem Description 在讲述DP算法的时候，一个经典的例子就是数塔问题，它是这样描述的：有如下所示的数塔，要求从顶层走到底层，若每一步只能走到相

迈不过友情╰/ 2021年12月13日 23:34/ 0 赞/ 318 阅读