HDU 2084 数塔(简单DP入门)

时间:2021-01-15 09:56:14

数塔

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

Total Submission(s): 41852    Accepted Submission(s): 24820

Problem Description
在讲述DP算法的时候,一个经典的例子就是数塔问题,它是这样描述的:
有如下所示的数塔,要求从顶层走到底层,若每一步只能走到相邻的结点,则经过的结点的数字之和最大是多少? HDU 2084 数塔(简单DP入门) 已经告诉你了,这是个DP的题目,你能AC吗?
 
Input
输入数据首先包括一个整数C,表示测试实例的个数,每个测试实例的第一行是一个整数N(1 <= N <= 100),表示数塔的高度,接下来用N行数字表示数塔,其中第i行有个i个整数,且所有的整数均在区间[0,99]内。
 
Output
对于每个测试实例,输出可能得到的最大和,每个实例的输出占一行。
 
Sample Input
1
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
 
Sample Output
30
 
Source
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2084
分析:DP入门题,学长好像讲了DFS写法,没怎么听,下次补上!
 #include<stdio.h>
int main()
{
int C,i,j,N;
int a[][];
while(scanf("%d",&C)==)
{
while(C--)
{
scanf("%d",&N);
for(i=;i<N;i++)
for(j=;j<=i;j++)
scanf("%d",&a[i][j]);
for(i=N-;i>=;i--)
{
for(j=;j<=i;j++)
{
if(a[i][j]+a[i-][j]>a[i][j+]+a[i-][j])
a[i-][j]=a[i][j]+a[i-][j];
else
a[i-][j]=a[i][j+]+a[i-][j];
}
}
printf("%d\n",a[][]);
}
}
return ;
}

以上这种是别人的想法,下面我来说说我对DP的理解!

解题思路:
用二维数组存放数字三角形。
D( r, j) : 第r行第 j 个数字(r,j从1开始算)
MaxSum(r, j) : 从D(r,j)到底边的各条路径中,
最佳路径的数字之和。
问题:求 MaxSum(1,1)
典型的递归问题。
D(r, j)出发,下一步只能走D(r+1,j)或者D(r+1, j+1)。故对于N行的三角形:
if ( r == N)
MaxSum(r,j) = D(r,j)
else
MaxSum( r, j) = Max{ MaxSum(r+1,j), MaxSum(r+1,j+1) } + D(r,j)

并且每算出一个MaxSum(r,j)就保存起来,下次用
到其值的时候直接取用,则可免去重复计算。那么
可以用O(n 2 )时间完成计算。因为三角形的数字总
数是 n(n+1)/2!

下面给出我的代码:
 #include <bits/stdc++.h>
using namespace std;
int dp[][];
int maxSum[][];
int n;
int MaxSum(int i,int j)
{
if(maxSum[i][j]!=-)
return maxSum[i][j];
if(i==n)
maxSum[i][j]=dp[i][j];
else
{
int x=MaxSum(i+,j);
int y=MaxSum(i+,j+);
maxSum[i][j]=max(x,y)+dp[i][j];
}
return maxSum[i][j];
}
int main()
{
int T;
while(cin>>T)
{
while(T--)
{
cin>>n;
for(int i=;i<=n;i++)
for(int j=;j<=i;j++)
{
cin>>dp[i][j];
maxSum[i][j]=-;
}
cout<<MaxSum(,)<<endl;
}
}
return ;
}

HDU 2084 数塔(简单DP入门)的更多相关文章

  1. hdu 2084 数塔 &lpar;简单dp&rpar;

    http://acm.hdu.edu.cn/showproblem.php?pid=2084 数塔 Time Limit: 1000/1000 MS (Java/Others)    Memory L ...

  2. HDU 2084 数塔 (dp)

    题目链接 Problem Description 在讲述DP算法的时候,一个经典的例子就是数塔问题,它是这样描述的: 有如下所示的数塔,要求从顶层走到底层,若每一步只能走到相邻的结点,则经过的结点的数 ...

  3. HDU 2084 数塔 &lpar;DP&rpar;

    数塔 Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u Submit Status Pr ...

  4. hdu 2084 数塔(简单dp)

    题目 简单dp //简单的dp #include<stdio.h> #include<string.h> #include<algorithm> using nam ...

  5. 题解报告:hdu 2084 数塔(递推dp)

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2084 Problem Description 在讲述DP算法的时候,一个经典的例子就是数塔问题,它是这 ...

  6. HDU 2084 数塔(动态规划)

    数塔 http://acm.hdu.edu.cn/showproblem.php?pid=2084 Problem Description 在讲述DP算法的时候,一个经典的例子就是数塔问题,它是这样描 ...

  7. HDOJ&period;2084 数塔(DP)

    数塔 点我挑战题目 题意分析 DP的思想,自上而下计算. [这几天比较忙 有空补上] 代码总览 /* Title:HDOJ.2084 Author:pengwill Date:2017-1-14 */ ...

  8. ACM 杭电HDU 2084 数塔 &lbrack;解题报告&rsqb;

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

  9. HDU 2084 数塔 (动态规划DP)

    原题链接:http://acm.hdu.edu.cn/showproblem.php?pid=2084 题目分析:此题采用动态规划自底向上计算,如果我们要知道所走之和最大,那么最后一步肯定是走最后一排 ...

随机推荐

  1. elasticsearch客户端连接选择

    elasticsearch支持两种协议: http协议. Native Elasticsearch binary protocol(本地elasticsearch二进制协议):elasticsearc ...

  2. php的rss订阅

    一般来说我们很少自己造*,读取rss还是用git上的开源库吧 https://github.com/dg/rss-php 这个开源库不能读取博客园的rss订阅,新浪微博的格式显示有问题. 博客园的订 ...

  3. &lbrack;AngularJS&rsqb; Introduction to ui-router

    Introduce to basic $stateProvider.state() with $stateParams services. Understand how nested router w ...

  4. CollapsingToolbarLayout

    CollapsingToolbarLayout作用是提供了一个可以折叠的Toolbar,它继承至FrameLayout,给它设置layout_scrollFlags,它可以控制包含在Collapsin ...

  5. SyntaxError&colon; Non-ASCII character '&bsol;xe2' in file 编码错误

    Editing .py file in the Notepad: But when run in the PowerShell, I found the follwing error: It seem ...

  6. CSS的使用方法

    参考资料:http://css.cuishifeng.cn/ 一.CSS的四种引入方式 1.行内式 行内式是在标记的style属性中设定CSS样式.这种方式没有体现出CSS的优势,不推荐使用(与链接式 ...

  7. &lbrack;Ynoi2018&rsqb;末日时在做什么&quest;有没有空&quest;可以来拯救吗&quest;

    这道题真的超级...毒瘤 + 卡常 + 耗 RP 啊... 传送门 noteskey 题解看 shadowice 大仙 的 code 如果发现自己 T 掉了,别心急,洗把脸再交一遍试试... //by ...

  8. UVA215-Spreadsheet Calculator(模拟&plus;拓扑排序)

    Problem UVA215-Spreadsheet Calculator Accept:401  Submit:2013 Time Limit: 3000 mSec Problem Descript ...

  9. vue深入响应式原理

    vue深入响应式原理 深入响应式原理 — Vue.jshttps://cn.vuejs.org/v2/guide/reactivity.html 注意:这里说的响应式不是bootsharp那种前端UI ...

  10. Ubuntu 上安装QTAV第三方视频库

    安装QtAV的基本环境: sudo apt-get install build-essential sudo apt-get install libgl1-mesa-dev sudo apt-get ...