首页 > 代码库 > 动态规划习题：数字三角形
动态规划习题：数字三角形
问题描述
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路
径，把路径上面的数加起来可以得到一个和，和最大的路径称为最佳路径。你的任务就是求
出最佳路径上的数字之和。
注意：路径上的每一步只能从一个数走到下一层上和它最近的左边的数或者右边的数。
输入数据
输入的第一行是一个整数 N (1 < N <= 100)，给出三角形的行数。下面的 N行给出数字
三角形。数字三角形上的数的范围都在 0和 100之间。
我们形象的描述下这个问题，把每一层的数字，描述为金子数量，那么我们就是要选择一条最优的路径，获得最大的金子数量。
思路：从第0层到最后4层来递归，当我在第0层，思考往左还是往右的时候，实际上这就是一个选择，类似0,1背包的放还是不放。那么第一层的最优解=往左走的最优解和往右走的最优解中的最大值+第0层的金子，那么这里也就产生了两个最优子结构，所以可以得出状态转移方程：f(i,j)=max(f(i+1,j),f(i+1,j+1))+Tri[i][j]
1 #include <iostream> 2 using namespace std; 3 int mydp[5][5]; 4 int Tri[5][5]={{7}, 5 {3,8}, 6 {8,1,0}, 7 {2,7,4,4}, 8 {4,5,2,6,5}}; 9 int get_max37(int a,int b)10 {11 return a>b?a:b;12 }13 int max_sum(int i,int j)14 {15 int retMax;16 if(mydp[i][j]!=-1)17 {18 retMax=mydp[i][j];19 }20 //边界条件21 else if(i==4)22 {23 retMax=Tri[i][j];24 }25 else26 {27 retMax=get_max37(max_sum(i+1,j),max_sum(i+1,j+1))+Tri[i][j];28 }29 mydp[i][j]=retMax;30 return retMax;31 }32 int main() 33 {34 for (int i=0;i<5;++i)35 {36 for (int j=0;j<5;++j)37 {38 mydp[i][j]=-1;39 }40 }41 cout<<max_sum(0,0);42 system("pause");43 return 0;44 }
动态规划习题：数字三角形
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。