动态规划的概述
wiki的定义写的很好
动态规划(英语：Dynamic programming，简称DP)是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再合并子问题的解以得出原问题的解。通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。
个人理解：撇去规范的定义，动态规划(dynamic programming)的本质很简单，就是一个递推算法，特点是牺牲空间换取时间。
动态规划的适用情况
问题具备3个主要特点：
- 最优子结构: 如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。
- 重叠子问题: 子问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。
- 无后效性: 即子问题的解一旦确定，就不再改变，不受在这之后、包含它的更大的问题的求解决策影响。
个人理解：
一个问题可以分解成子问题的组合，那么这个问题通常可以用递归的形式解决（最优子结构），但是递归时我们发现有些子问题是重复的（重叠子问题），为了节省时间，我们不想重复计算这些子问题，有什么办法可以“记忆”这些求过的解呢？
在满足无后效性特点的情况下，其实我们求解的时候可以反过来用递推的方式去保存出现的解，这样递推地求取最终的动态规划结果。最后获取结果其实就是去查表，表格里保存着递推过程中获取的解。
实例
有很多经典问题，用动态规划可以获取可行解。例如：
它们的讲解在网上可以找到非常丰富的资源，本文就不在详述。
本文主要结合博主在刷leetcode过程中碰到的DP类问题来讲述DP算法。
问题描述
给定一个向量a[N], a[i]代表一双袜子在第i天的价格，你可以在低价的时候买入袜子，在高价的时候卖出袜子来获取利润，问在最多可以完成k次交易的情况下，最大可以获取多少利润。
注：手上最多可以持有一双袜子，即结束上一次交易前，不可以买入新袜子。
问题分析
这个问题直觉上看着就像一个动态规划问题。
阿光：怎么看出来，我怎么看不出来？
我：直觉
阿光：直觉是什么鬼？
我：作为程序员，要培养那些抽象的看问题的直觉。
阿光：。。。。。
我：多学，多练
洲妹：这个B装的我服！
我: 2
阿光：8
我们用动态规划的假设去套套看，假设最大利润函数是L(n, k):n表示只在前n天交易，k表示交易次数。那么L(n,k)是不是可以表示成f(L(n-1, k),L(n,k-1))的形式呢，也就是一个可递归的形式呢？
我刚开始分析的时候想了半天没想出来，后来实在忍不住看了一下leetcode上的discuss，看到别人代码一下子就豁然开朗了。简单的用标量L(n,k)是不行的，应该采用向量的形式，即(buy(n,k), sell(n,k))
其中sell(n,k)即表示n天内完成k次交易的最大利润，而buy(n,k)表示n天内完成k-1次交易同时减去买一双袜子的钱后手上的最大利润，本质上buy(n,k)其实是为了获取第k次购买时购买的最低价。
这样递归的形式就很清晰了:
buy(i,k) = max(buy(i-1,k), sell(i-1,k-1)-a[i])
sell(i,k) = max(sell(i-1, k), buy(i-1,k)+a[i])
对上述递推的理解也很简单
- buy: 要么第i天买(sell(i-1,k-1)-a[i]),要么不在第i天买，也就是在前i-1天内已经买了(buy(i-1,k))
- sell: 要么在第i天卖(buy(i-1,k)+a[i])，要么在前i-1内已卖出(sell(i-1, k))
那么我们就得到了一个递归的形式，反向地也就得到了递推形式，这样就得到了一个时间复杂度O(kn)的动态规划算法。
代码如下：
int maxProfit(int k, vector<int>& prices) {
int n = prices.size();
if (k>=n/2) {
int sum = 0;
for(int i=1; i<n; i++){
if(prices[i] > prices[i-1]){
sum += prices[i] - prices[i-1];
}
}
return sum;
}
vector<int> buy(k+1, INT_MIN), sale(k+1, 0);
for(int i=0; i<n; i++){
for(int j=1; j<=k; j++){
buy[j] = max(buy[j], sale[j-1]-prices[i]);
sale[j] = max(sale[j], buy[j] + prices[i]);
}
}
return sale[k];
}
结语
记住动态规划就是一个递推算法，特点是牺牲空间换取时间。
阿光，洲妹，学到了么？
ps： 码字好累
暗号： “凯” 请阿光对接！