51nod 1002数塔取数 dp

不念不忘少年蓝@ 2022-08-20 13:11 145阅读 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 条评论，145人围观）

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

相关阅读

相关 51nod 1002数塔取数 dp

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

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

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

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

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

相关 51nod 1083 矩阵取数问题

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

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

相关 51Nod--1015 水仙花数

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

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

相关数塔——DP算法

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

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

相关 hdu 2084 数塔（基础dp）

数塔Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others

Bertha 。/ 2022年06月07日 05:46/ 0 赞/ 163 阅读

相关 HDU-2084-数塔（dp入门）

数塔 Problem Description 在讲述DP算法的时候，一个经典的例子就是数塔问题，它是这样描述的：有如下所示的数塔，

秒速五厘米/ 2022年05月27日 06:57/ 0 赞/ 185 阅读

相关 TOJ 4674 数塔II DP

4674: 数塔II 描述有如下所示的数塔，要求从顶层走到底层，若每一步只能走到相邻的结点，则经过的结点的数字之和最大是多少，并输出一条路径。 7 3 8

心已赠人/ 2022年05月18日 10:59/ 0 赞/ 163 阅读

相关 HDU2084 数塔 (dp算法）

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

深碍√TFBOYSˉ_/ 2022年05月08日 09:08/ 0 赞/ 184 阅读

相关 HDU2084：数塔(DP)

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

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