题目描述 注意：路径上的每一步只能从一个数走到下一层上和它最近的左边的那个数或者右边的那个数。 输入格式 输出格式 样例 精髓: 以样例为例，可以发现动态规划明显优于贪心。 贪心:
数字三角形
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最大的和。
输入的是一行是一个整数N (1 < N <= 100)，给出三角形的行数。下面的N行给出数字三角形。数字三角形上的数的范围都在0和100之间。
输出最大的和。
样例输入
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
样例输出
30
此题是经典的动态规划题，那为什么不用贪心呢？
如果用贪心的话，我们应从第一行第一列的数开始顺推，正下方和右下方的数字谁大就加上。
如果用动态规划的话，我们应从倒数第二行开始逆推，左下数字的最大路径和和右下数字的最大路径和谁大就加谁。
动态规划:
参考代码:#include<cstdio> #include<algorithm> using namespace std; int main() { int n,a[105][105],dp[105][105];//dp[i][j]为状态，意思是a[i][j]到最 scanf("%d",&n); //后一行的最大路径和 for(int i=1;i<=n;i++) { for(int j=1;j<=i;j++) { scanf("%d",&a[i][j]); } } for(int j=1;j<=n;j++) { dp[n][j]=a[n][j];//初始化 } for(int i=n-1;i>=1;i--) { for(int j=1;j<=i;j++) { dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+a[i][j];//状态转移方 } //程 } printf("%d",dp[1][1]); return 0; }
本网页所有视频内容由 imoviebox边看边下-网页视频下载, iurlBox网页地址收藏管理器 下载并得到。
ImovieBox网页视频下载器 下载地址: ImovieBox网页视频下载器-最新版本下载
本文章由: imapbox邮箱云存储,邮箱网盘,ImageBox 图片批量下载器,网页图片批量下载专家,网页图片批量下载器,获取到文章图片,imoviebox网页视频批量下载器,下载视频内容,为您提供.
阅读和此文章类似的: 全球云计算
官方软件产品操作指南 (170)
