数塔——DP算法

古城微笑少年丶 2022-06-12 01:41 234阅读 0赞

在讲述DP算法的时候，一个经典的例子就是数塔问题，它是这样描述的：

有如下所示的数塔，要求从顶层走到底层，若每一步只能走到相邻的结点，则经过的结点的数字之和最大是多少？  
![这里写图片描述][SouthEast]

**动态规划问题**  
显然动态转移方程为：dp\[i\]\[j\]=max(dp\[i+1\]\[j\],dp\[i+1\]\[j+1\]);dp\[i\]\[j\]+=a\[i\]\[j\];  
个人理解就是分配空间，为空间置零，我的方法是从最后一行开始查询。具体看我的代码。

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const int MAXN=102;
    int a[MAXN][MAXN];
    int dp[MAXN][MAXN];
    int main()
    {
        int T;
        scanf("%d",&T);
        while(T--)
        {
            memset(dp,0,sizeof(dp));
            memset(a,0,sizeof(a));
    
            int n;
            scanf("%d",&n);
            for(int i=1;i<=n;i++)
                for(int j=1;j<=i;j++)
                    scanf("%d",&a[i][j]);
    
            for(int i=1;i<=n;i++)
                dp[n][i]=a[n][i];
    
            for(int i=n-1;i>=0;i--)
            {
                for(int j=1;j<=i;j++)
                {
                        dp[i][j]=max(dp[i+1][j],dp[i+1][j+1]);
                        dp[i][j]+=a[i][j];
                }
            }
            printf("%d\n",dp[1][1]);
    
        }
        return 0;
    }

[SouthEast]: /images/20220612/474e734bf24e4aa2b250cd03fef0885e.png

发表评论取消回复

表情：

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

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

相关阅读

相关关于dp数塔类问题及其变形

数塔问题是一个很经典的问题，它是每个人学习动态规划的入门题，数塔问题也是理解和分析动态规划的经典，它里面所反映出现的性质也是相对于其他动态规划题目更明显，最优子结构和无后效性在

悠悠/ 2022年09月20日 11:12/ 0 赞/ 199 阅读

相关 DP之数塔模型poj1157

题目：[poj1157LITTLE SHOP OF FLOWERS][poj1157_LITTLE SHOP OF FLOWERS] 题意：假设以最美观的方式布置花

水深无声/ 2022年08月27日 15:56/ 0 赞/ 167 阅读

相关 51nod 1002数塔取数 dp

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

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

相关数塔——DP算法

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

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

相关 hdu 2084 数塔（基础dp）

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

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

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

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

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

相关 TOJ 4674 数塔II DP

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

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

相关 HDU2084 数塔 (dp算法）

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

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

相关 HDU2084：数塔(DP)

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

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

相关免费馅饼 HDU-1176【数塔+DP】题解

目录 1.题目 2.思路 3.代码 1.题目都说天上不会掉馅饼，但有一天gameb

╰半橙微兮°/ 2021年07月24日 14:56/ 0 赞/ 405 阅读