【递推DP】POJ1163The Triangle
DP 递推 Triangle
2023-09-11 14:20:43 时间
题目链接:http://poj.org/problem?id=1163
事实上这个题目有非常多解法,可是我们能够看下这个用一位数组的高效动规解法,这个我上课时老师讲的,非常不错。
先保存最后一行4 5 2 6 5,然后更新最大值7=max(4,5)+2;依次类推,非常显然,我们就能够得到状态转移方程:dp[j]=max(dp[j],dp[j+1])+a[i][j];
这样这个题目就非常好攻克了;
#include<iostream> #include<string> #include<cstdio> #include<cstring> #include<queue> #include<map> #include<stack> #include<set> #include<vector> #include<algorithm> #define LL long long using namespace std; int a[102][102]; int n; int dp[102]; int main() { while(~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[i]=a[n][i]; // 将最后一行保存; for(int i=n-1;i>0;i--){ for(int j=1;j<=i;j++){ dp[j]=max(dp[j],dp[j+1])+a[i][j]; // 更新数据; } } printf("%d\n",dp[1]); } return 0; }
相关文章
- nyoj 括号匹配(二) 15 (区间dp) 好题
- poj2411 Mondriaan's Dream 状压DP
- Android px、dp、sp之间相互转换
- Android 中像素px和dp的转化
- DL之CNN:卷积神经网络算法应用之卷积神经网络实践技巧(DA/DP/WI/BN/H/O/R)、优化技术经验之详细攻略
- HDU 3001 Travelling (三进制状态压缩 DP)
- Codeforces 474D Flowers dp(水
- 概率统计(DP)
- POJ 3934 Queue(DP)
- hdu2571 命运 动态规划Dp
- 区间dp模型之括号匹配打印路径 poj(1141)
- HDU4960Another OCD Patient(间隙dp,后座DP)
- PAT 1040 Longest Symmetric String[dp][难]