vlambda博客
学习文章列表

首先是将大问题进行拆分，动态规划题目我们可以把题目要求的解作为一个大的问题，然后对这个大问题进行划分，分成一步一步的可以通过递推或者递归实现的。这个小问题往往是一个值，这个值我们通常是用一维数组或者是二维数组来保存的。

如果你成功将一个大问题拆分成了小问题，也就是说你已经知道了只有一种情况时最小结构的解是什么，那么你就可以以这个最小的结构为基础向上推导，进而得到一种不同层级解之间的关系。这有点像数学归纳法。就是把你拆分的一步步之间的关系使用数学的推导公式来表示出来，这个公式用递归是很容易实现的。

最后既然动态规划要使用到递归，那么就不得不考虑边界问题了。所以边界问题也是动态规划必须考虑的。

所以总结一下，要想解决一个动态规划问题，下面的三要素是必须的：

• 最优子结构，上文提到的拆分到的最小的那一步。

• 边界 ，涉及到递归必须考虑的问题。

• 状态转移方程 ，拆分过程中不同步之间的关系。

乍看之下，动态规划其实蛮暴力的，使用动态规划往往需要经过繁琐的计算，最后才一举解决问题，有点像武侠小说中经常看到的那种先蓄力在发动的绝招一样。但是解决动态规划问题是必须要注意的一点是，小问题的解一旦被计算出来，就要存储起来，不要重复计算，如果你忘了这一点，在实际的生产环境中，你的代码将会是服务器的灾难。动态规划运用得当，可以高效的解决问题。

下面我们就按照所说的三步来解决题目。

第一步找最优子结构，把问题拆分

我们拿到这个题目，从题目中得到的关键信息：从顶部到底部，最大数字之和。为什么这两个信息重要呢？"从顶部到底部"基本定格了我们找最优结构的方向，也就是从第N层开始。"最大数字之和"就是我们所说的“大问题”。所以我们要拆分的小问题就是这个基础值。

首先我们想第N层的节点值，N层三角形第N层肯定只有一个数值，一层的时候（用题目中的三角为例）：

这个数组我们怎么表示呢？可以用一个一维数据D[i]表示。

那如果有两层呢？

两层的时候就有两种路径，两个和，分别是7+3和7+8。显然我们取两个值中的大的值作为最终解。这里发现一个问题，表示数值的大小不能用一维数组了，更好是采用二维数组D[i][j](表示第i行第j个数字)。把当前的位置[i，j]看成一个状态,然后定义状态[i，j]的指标函数maxSum(i,j)为从位置[i，j]出发时能得到的最大和。

可以看出每走第i行第j列时有两种后续:向左下或者向右下。不同状态之间转移从[i，j]出发有两种决策。如果往左走，则走到[i+1,j]，后需要求从[i+1，j]出发后能得到的最大和，即maxSum(i+1,j)。往右走之后需要求解maxSum(i+1,j+1)。由于可以在这两个决策中自由选择，所以应选择maxSum(i+1,j)和maxSum(i+1,j+1)中较大的一个。由此得到如下状态转移方程：

maxSum(i,j) = D(i,j) + max{maxSum(i+1,j),maxSum(i+1,j+1)}

因为最后一行可以确定，所以当做边界。我们需要求解的是maxSum(1, 1)，所以上题的递归大概是这个样子：

if(i == N)    maxSum(i,j) = D[i][j]else    maxSum(i, j) = Max{maxSum(i+1, j), maxSum(i, j+1)} + D[i][j]

所以上面问题的核心实现JAVA版：

public int getMax(){ int MAX = 101; //存储数字三角形 int[][] D = new int[MAX][MAX];  //n表示层数 int n;  int i = 0; int j = 0; int maxSum = getMaxSum(D,n,i,j); return maxSum; } public int getMaxSum(int[][] D,int n,int i,int j){ if(i == n){ return D[i][j]; } int x = getMaxSum(D,n,i+1,j); int y = getMaxSum(D,n,i+1,j+1); return Math.max(x,y)+D[i][j];  }

更简单的写法：

return D[i][j]+(i==n? 0 : max(maxSum(i+1,j),maxSum(i+1,j+1)));

标准AC的答案，在这C语言版本：

#include <iostream>#include <algorithm>#define MAX 101
use namespace std;int D[MAX][MAX];int n;
int maxSum(int i, int j){ if(i == N){ return D[i][j]; } int x = maxSum(i + 1, j); int y = maxSum(i + 1, j + 1); return max(x, y) + D[i][j];}
int main(){ int i, j; cin >> n; for(i = 1; i <= N; ++i){ for(j = 1; j <= i; ++j) cin >> D[i][j]; } cout << maxSum(1, 1) << endl;}

 你以为这样就结束了吗？你想过上面算法的时间复杂度了吗？举个例子说明上面递归的流程，示例：

按照上面的递归这个例子的调用流程如下：

由此可见这个算法的时间复杂度是2^N。

这样递归是正确的，但时间效率太低，其原因在于重复计算。在MAX(1,1)对应的调用关系树中，MAX(3,2)被计算了两次（一次是MAX(2,1)需要的，一次是MAX(2,2)需要的）。也许读者会认为重复算一两个数没有太大影响，但事实是：这样的重复不是单个结点，而是一颗子树。如果原来的三角形有n层，则调用关系树也会有n层，一共有2^n-1个结点。

现在思考一下，如果每算出一个MaxSum(r,j)就保存起来，下次用到其值的时候直接取用，就可以免去重复计算。那么 可以用O(n2)时间完成计算。因为三角形的数字总 数是 n(n+1)/2。

#include<iostream>#include<algorithm>using namespace std;#define MAX 101int D[MAX][MAX];int n;int maxSum[MAX][MAX];
int MaxSum(int i,int j){ if(maxSum[i][j] != -1)//这个数字的最大值已经被求出来了 return maxSum[i][j]; if(i == n)//如果i==n，那就说明它已经是最后一行的那个数字了， 那最大和就是那个数字它自己 maxSum[i][j] = D[i][j]; else //否则呢，我们就要算一下 它正下方的那个数字走到底边得到的最大和是什么 { int x = MaxSum(i + 1, j); int y = MaxSum(i + 1, j + 1); maxSum[i][j] = max(x,y) + D[i][j]; } return maxSum[i][j];}
int main(){ int i,j; cin >> n; for(i = 1 ; i <= n ; i++) for(j = 1 ; j <= i; j++) { cin >> D[i][j]; maxSum[i][j] = -1; } cout << MaxSum(1,1) << endl;}

时间复杂度就变成了O(n^2)，因为这个数字三角形里面数字的总数是n(n+1)再除以2，对于每一个数字 它到底边的最大和都只需要算一次就行了。那这样需要算的总的次数就是这么多。时间复杂度就是n^2了。

这是一种减少时间复杂度的方法，当然动态规划的问题也可以把递归转换成递推的方式，可以减少空间复杂度，感兴趣的可以网上找找对应的实现。