【算法学习笔记】31.动态规划 SJTU OJ 1320 numtri
Description
Consider the number triangle shown below. Write a program that calculates the highest sum of numbers that can be passed on a route that starts at the top and ends somewhere on the base. Each step can go either diagonally down to the left or diagonally down to the right.
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
In the sample above, the route from 7 to 3 to 8 to 7 to 5 produces the highest sum: 30.
Input Format
The first line contains R (1 <= R <= 1000), the number of rows. Each subsequent line contains the integers for that particular row of the triangle. All the supplied integers are non-negative and no larger than 100.
Output Format
A single line containing the largest sum using the traversal specified.
Sample Input:
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
Sample Output:
30
利用动态规划的思想,可以从第二排开始更新节点,使节点的值变为从它之前选取的最大值.语言叙述比较麻烦,以样例来说就是
7
10 15
18 16 15
20 25 20 19
24 30 27 26 24
所以选最后一排里最大的那个数即可,但是这种更新方法比较麻烦的是要考虑边界情况,比如 每行的两个端点的处理比较麻烦
根本原因是因为" 找到一个节点的前驱节点的过程与节点位置有关 "
因此想到 找一个节点的后继节点 是不是更方便一点? 是的.因为所有的节点都有两个子节点.
所以更新过程变为了从倒数第二排开始向第一排更新
最后一排不动:4 5 2 6 5
倒数第二排开始更新:
7 12 10 10
20 13 10
23 21
30
所以更新之后的第一个节点即是答案,也避免了寻找最大值的过程, 非常简便.
这个算法属于动态规划的思想, 因为它存储了可能重复计算的结果(或者说,它在本质上不存在重复计算),每一个阶段就是每一行的状态集合,
每一个点的状态S[x]就是指,在原树的基础上从这个点开始出发到最后的路径里最大的和.
状态转移方程就是 S[x] = R[x] + max(S[x.leftson],S[x.rightson])
计算状态时 要用到x的下一层 也暗示了我们要从底向上遍历.
代码如下:
#include <iostream> using namespace std; int R[1000000] = {0}; int N; inline int getLayFirstId(int layId){ return (1+layId-1)*(layId-1)/2 + 1; } inline int getLeftSon(int node , int layId){ return getLayFirstId(layId+1) + node - getLayFirstId(layId); } //从 curId开始向下选择 curLay是当前行 curSum 是之前的和 int Calc(int curId, int curLay, int curSum){ int left = getLeftSon(curId,curLay); int right = left+1; if(curLay == N-1) return R[left] > R[right] ? curSum + R[left] : curSum + R[right]; int lsum = Calc(left,curLay+1,curSum) + R[curId]; int rsum = Calc(right,curLay+1,curSum) + R[curId]; return lsum > rsum ? lsum : rsum; } inline int getMAX(int a, int b){ return a>b?a:b; } //从N-1排开始更新 inline void updateLayer(int layId){ for (int i = 0; i < layId; ++i) { int node = getLayFirstId(layId)+i; int left = getLeftSon(node,layId); int right = left+1; R[node] += getMAX(R[left],R[right]); } } int main(int argc, char const *argv[]) { cin>>N; for (int i = 1; i <= N*(N+1)/2; ++i) cin>>R[i]; //从R[1]开始存储 为了计算方便 for (int k = N-1; k >= 1; k--) updateLayer(k); cout<<R[1]<<endl; return 0; }
PS1:此题用贪心法可以得60分, 贪心策略就是在决定选左还是选右时,先进行试探,然后根据左的左 左的右 右的左 右的右 这四个节点来进行决策.
PS2:此题也可以用分治法来进行暴力搜索DFS 在DFS的过程中此题不能用回溯法,因为所有解都是可行解,我们找的是最优解,最优解一般会想到用分支界限法来剪枝,但是此题节点值并没有顺序(不像埃及分数那样),所以也不可以.即使可以也会有重复计算.
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。