首页 > 代码库 > [动态规划]数字三角形
[动态规划]数字三角形
动态规划一直是一个很头疼的问题啊。
最近在看这方面的东西，记录一下刘汝佳书里的动态规划章节里的数字三角形题目。
这道题很基础，但总结的三个动态规划很清晰。
有一个由非负整数组成的三角形，第一行只有一个数，除了最下行之外每个数的左下方和右下方各有一个数，形如： 1 3 2 4 10 1 4 3 2 20 每个结点都可到它左右子结点，例如3可以到4也可以到10. 从第一行开始每次可以往左下或右下走一格，直到走到最下，把沿途结点的值相加，如何走才能得到最大值。
如果遍历的话，n层会有2的n次方种可能性，显然规模太大。所以换一种思路。
其实最难的是跨出第一步，也就是在结点1，是要向左走还是向右走。因此对于1来讲，如果它能够知道向左跟向右现在的值是多少，它就可以迈出第一步。
我们用i,j表示第i层第j个结点
因此就有 d(i,j)=value(i,j)+max{d(i+1,j),d(i+1,j+1)}
这就是这道题的状态转移方程。
算法1：递归
int d (int i,int j){ return a[i][j] + (i==n?0 : d(i+1,j)>?d(i+1,j+1)); }
嗯。。思路很直接。。语法很简练。。就是耗时会很长，而且层数一多可能就栈溢出了。
算法2：递推
int i,j; for(j=1;j<=n;j++) d[n][j]=a[n][j]; for(i=n-1;i>=1;i++) for(j=1;j<=i;j++) d[i][j]=a[i][j]+d[i+1][j]>?d[i+1][j+1];
用二维数组d[i][j]保存状态，用递推的方法从i=1开始，因此当计算d(i,j)需要d(i-1,j) 和d(i-1,j+1)时这两个状态已经计算好了。
算法3：记忆化搜索
int d(int i,int j){ if(d[i][j]>=0) return d[i][j]; return a[i][j]=a[i][j]+(i==n?0:d(i+1,j)>?d(i+1,j+1);
这是对算法1的改进，算法1没有对状态进行保存，这里借用d[i][j]来保存状态，并且用 -1 来表示d[i][j]状态还没有被计算过，因此当>=0时就可以直接返回。
[动态规划]数字三角形
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。