最近在leetcode和牛客网上刷题，经常碰到一些和动态规划相关的问题，虽然动态规划的思路貌似不难，但是在具体的应用场景上却总是困扰我，很难巧妙结合，决定写一篇博客来记录下我对动态规划的理解和遇到的各种问题以及如果将理论与实际编码结合。
这篇博客不是一次写成的，我会陆续将我遇到的、我认为有代表性的动态规划问题和解法在此进行总结。
动态规划
动态规划（Dynamic programming,简称DP）通过把原问题分解为相对简单的子问题进行求解。动态规划的思想很简单，就是把原问题分解为一系列子问题，然后由这些子问题逐渐组成更复杂的原问题。通常，子问题之间十分相似，动态规划试图仅解决每个子问题一次，从而减少计算量。一旦某个子问题已经解出，就将其记忆化存储，下次再遇到相同问题时可以查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。（以上参考维基百科定义）
其实对于我来说，第一次接触动态规划是在大学时的数据结构课堂上，当时老师在求解fobinacci数列采用递归算法，这种递归算法存在大量重复的子问题。比如求f（10），因为f（10）=f（9）+f（8），而f（9）=f（8）+f（7），可以看到，这里需要两次求f（8），继续向下扩展，复杂度呈指数增加。把这些递归算法用迭代替换问题就可以得到解决，老师当时说这种用迭代替换递归的思路就叫动态规划，这个印象也在我脑海里很多年。
动态规划其实适用于解决这样的问题，这类问题需要包含三类性质：
- 重叠子问题。它将问题重新组合成子问题。为了避免多次解决这些子问题，它们的结果都逐渐被计算并被保存，从简单的问题直到整个问题都被解决。因此，动态规划保存递归时的结果，因而不会在解决同样的问题时花费时间。
- 无后效性。即子问题的解一旦确定，就不再改变，不受在这之后、包含它的更大的问题的求解决策影响。
- 子问题重叠。子问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的效率。
接下来我们参照两个实际例子来理解。
斐波那契数列
最简单的计算算法，就是递归了，如下所示。
int func(int n){
if(n==0||n==1)
return 1;
return func(n-1)+func(n-2);
}
当n=5时，计算过程如下：
- fib(5)
- fib(4) + fib(3)
- (fib(3) + fib(2)) + (fib(2) + fib(1))
- ((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
- (((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
由上面可以看到，这种算法计算了大量的重复的子问题，因此效率不高，事实上它的运算时间是指数增长的。改进的方法可以是将中间结果存起来，也就是所谓的将递归变成迭代，代码如下所示。
int func(int n){
if(n==0||n==1)
return 1;
int res=1,res1=1,temp;
for(i=1;i<n;i++){
temp=res;
res=res+res1;
res1=temp1;
}
return res;
}
背包问题
背包问题可以这样描述：有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。
研究一个动态规划问题，首先我们需要确定它的状态和状态转移方程。对于背包问题来说，它的状态和状态转移方程分别如下。
状态（由子问题定义）：f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。
状态转移方程：f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}。
这里需要解释一下状态转移方程，其实对于前i个物品放入容量为v的背包来说，相较于前i-1个物品放入容量为v的背包来说，最大的差别就是第i个物品是不是放入背包，如果不放入背包，那么f[i][v]=f[i-1][v],如果第i个元素放入背包，那么f[i][v]=f[i-1][v-c[i]]+w[i],至于究竟放入还是不放入，就要看它们两个谁比较大了。接下来我们给你一个示例代码。
int func(vector<int> value,vector<int> weight,int w){
int *res;
res=new int[value.size()+1][w+1];//the variable res represents the results of sub-question.
for(int i=0;i<value.size()+1;i++){
res[i][0]=0;//when w=0,the total amount of value must be zero.
}
for(int j=0;j<w+1;j++){
res[0][j]=0;//when i=0,the total amount of value must be zero.
}
for(int i=0;i<value.size()+1;i++){
for(int j=0;j<w+1;j++){
if (i > 0 && j >= weights[i - 1]){
res[i][j]=max(res[i-1][v],res[i-1][v-c[i]]+w[i]);
}
}
}
return res[value.size()][w];
}
当然有很多种简化的编码方法，这里为了叙述一般意义下的做法，先初始化然后逐步将子问题向目标推进。