动态规划总结篇一
1.什么是动态规划
摘自leetcode
动态规划（英语：Dynamic programming，简称 DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题，并且记录所有子问题的结果，因此动态规划方法所耗时间往往远少于朴素解法。动态规划有自底向上和自顶向下两种解决问题的方式。自顶向下即记忆化递归，自底向上就是递推。
根据我的理解，动态规划就是保存之前计算过的子问题的解，通过子问题的解得出另一个子问题的解的方法。因为我们保存了之前计算过的子问题的解，而下一个子问题又可以通过之前保存的子问题的解进行一些转换(这个转换关系就是状态转移方程)得到，所以使用动态规划可以避免一些重复计算，极大的提高效率。
举个例子：有一个数组{1，2，3，4，5，6，7，8，9}；如果要你分别计算前 n 位数的和，你会怎么做呢（在这个例子中如果问题是让我们求出前九位数的的和，那么求出前五位数就是原问题的一个子问题，求出前六位数也是原问题的一个子问题），我想你可能会在计算前五位数时从一累加到五，计算前六位数时从一累加到六，计算前七位数时从一累加到七,以此类推。这是很正常的思路，也没有任何问题，但你有没有发现当你计算出了前五位数的和时，计算前六位数的和时就只需要用已经计算出了的前五位的和再加一个六就行了（当然这需要我们预先保存前五位数的和），这样我们就不用再从一加到六，极大的减小了计算量。再深入的思考一下，我们是不是从一开始就可以使用这种方法呢，保存前一位数的和，用于计算前两位数的和，再保存前两位数的和，用于计算前三位数的和，以此类推，直到计算出了全部数的值。（空间换时间）
如果你已经理解了上文的内容，那么你就可以得到通过一个子问题的解递推出下一个子问题的解的递推关系了，其实这就是状态转移方程。
特别要注意的是，要使用动态规划，问题必须具有 最优子结构性质 与 无后效性 ，否则是不能用的。
一个问题的求解方式应该不止是唯一的，那么什么情况下可以使用动态规划呢？
2.动态规划使用情景一——求极值问题
1.思路分析
求极值问题，如果问题中出现了最大，最小，最多，最少等字眼，你就可以考虑是否能使用动态规划。至于使用动态规划的一般步骤，我就不写了，网上写的好的太多了。
看个例子：
因为是力扣的题目，所以给个的力扣链接，感兴趣的可以看看：
给定两个字符串分别是text1与text2,求他们的最长公共子序列(只需要求出最长公共子序列的长度)。子序列可以是不连续的比如字符串abcdefg的子序列可以是ac,abd,abdefg,aceg。
举例：
text1:abcd与text2:ac的最长公共子序列是ac，长度为二；
text1:abcd与text2:ace的最长公共子序列是ac,长度为二；
text1:abcde与text2:abcgef的最长公共子序列是abce,长度为四；
分析题目我们就能找到关键字眼最长，且本题满足最优子结构性质与无后效性，所以可以使用动态规划。
注：下面举例只是便于理解，实际上动态规划的代码的执行并不是严格按下文进行的。
我们以text1:abcee与text2:acea举例。先拿出其中一个子问题进行分析如text1的一部分abc与text2的一部分ac,很显然他们的最长公共子序列是ac,最长公共子序列的长度是二，使用动态规划我们就要保存该值，即二。接着我们扩充子问题相原问题靠近，增加字符串长度得到text1:abce与text2:ace,因为新增的字符是相等的，所有我们很容易通过之前计算的子问题的解得到当前最长子序列为ace,最长公共子序列的长度是二加一为三。
接着扩充得到text1:abcee与text2:acea，新增的字符不相等，这时候当前问题的最长公共子序列的长度应该取text1:abce与text2:acea（text1减去最后一个字符与text2）的最长公共子序列的长度和text1:abcee与text2:ace（text2减去最后一个字符与text1）的最长公共子序列的长度里的最大值 。
想想为什么我们不和最后一个字符相同时采取一样的思路直接取text1:abce与text2:ace的最长公共子序列。这是因为一个字符串的最后一个字符虽然不能和另一个字符串的最后一个字符组成最长公共子序列，但却有可能和另一个字符串的倒数第二个字符组成最长公共子序列。举个例子：text1:acde与text2:acd的最后一个字符不相等但他们的最长公共子序列是text1:acd与text2:acd 组成的acd而并不是text1:acd与text2:ac组成的ac 。
至此我们可以归纳出状态转移方程：
当最后一个字符相等时，当前的最长公共子序列的长度为当前各字符串去掉一个字符时的最长公共子序列的长度加一。当不相等时为其中一个字符串去掉一个字符时的最长公共子序列的长度中的最大值。
即：
图片来自力扣：
2.代码实现
int longestCommonSubsequence(string text1, string text2) {
int n=text1.size();
int m=text2.size();
vector<vector<int>> dp(n+1,vector<int>(m+1,0));
for(int count=1;count<=n;++count){
char ch1=text1[count-1];
for(int count1=1;count1<=m;++count1){
char ch2=text2[count1-1];
if(ch1==ch2){
dp[count][count1]=dp[count-1][count1-1]+1;
}
else{
dp[count][count1]=max(dp[count-1][count1],dp[count][count1-1]);
}
}
}
return dp[n][m];
}
解释一下其中二维dp数组的含义。dp数组的两个下标分别表示两个字符串的前几个字符。如dp[5][6]的下标分别表示字符串一的前五个字符与字符串二的前六个字符，dp[5][6]的值表示字符串一的前五个字符与字符串二的前六个字符的最长公共子序列的长度。使用dp[i+1][j+1]就能表示所有字符串一的子串与字符串二的子串的组合，因为是组合，所以是乘法，i*j个组合，二维数组有（i+1) * (j+1)个元素，所以可以全部表示。（为什么要设为i+1与j+1，因为数组下标从0开始，下标要表示为前几个字符，所以设为i+1,j+1）。最后因为每一个组合的值都是通过之前的值通过状态转移方程得到的，所以自底向上的备忘录法就能解决。
3.动态规划使用情景二——计数，找路径问题
1.思路分析
按照惯例，给个力扣链接：
图片来自力扣：
机器人从图示位置出发，每次向下或向右走一步，不能往回走。需要走到星号的位置，问，总共有几种不同的方法走到星号所在的位置。
从结果出发考虑，如果机器人已经到了星号所示位置，那它是怎么过来的。很显然，它只能是从星号位置的上一个位置或星号位置的左边一个位置过来的。
如果机器人从开始位置到这两个位置的不同路径都是5种的话。那么到星号的不同路径就是10种。即这两个位置的不同路径相加。推广到每个位置，其实都是一样的。到当前位置的不同方法是到上一个位置与到左边一个位置的不同方法的和。（其实这题与青蛙跳台阶类似）
定义数组 dp[i][j]，下标分别表示从开始位置到第 i 行第 j 列的位置的不同路径。因为网格类似与一个二维数组，要表示每一个位置，所以要定义为二维数组。
得到状态转移方程 ：
图片来自力扣：
2.代码实现
int uniquePaths(int m, int n) {
if(m==0 || n==0){
return 1;
}
vector<vector<int>> dp(m,vector<int>(n,0));
for(int count=0;count<m;++count){
dp[count][0]=1;
}
for(int count=0;count<n;++count){
dp[0][count]=1;
}
for(int count=1;count<m;++count){
for(int count1=1;count1<n;++count1){
dp[count][count1]=dp[count-1][count1]+dp[count][count1-1];
}
}
return dp[m-1][n-1];
}
需要注意的是到第一行与到第一列的所有位置的不同方法都是一种，所以在最开始需要全部初始化为一。dp数组中的每一个值都是从上一行与左边的值得到的，所以可以使用自底向上的备忘录方法。
4.动态规划使用情景三——求存在性问题
1.思路分析
照例，给链接：
题目摘自力扣：
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
这个问题可以转化成是否可以从数组 nums 中选出一些数，使得这些数的和为所有数的和的一半。与经典的 0-1 背包问题类似。 求的是是否存在一些数，使得和为所有数的和的一半，是求存在性问题，考虑动态规划。
我们定义dp数组为 dp[i][j+1] ，下标 i 表示从前 i 个数中选元素，j 表示选出的元素和为 j 。dp[i][j+1] 的值表示能否从前 i 个数中选出部分元素使得和为 j 。
0-1 背包最关键的就在于对于背包里的每一个元素，都有选与不选两种状态，可以选，也可以不选。因此考虑状态转移方程的时候，对每一个 dp 的值，都要从这两个状态考虑。
现在思考当前选不选第n个数使得和为 j ，如果不选当前物品，前一个子问题的值是true(即之前n-1个元素中可以选出部分的元素使得和为 j ),则当前问题的值也为true,如果前一个子问题的值是false(即之前的元素中不能选出部分的元素使得和为 j ），那当前问题的值为false 。
如果前面的数中已经能选出部分元素使得和为 j 了，那当前这个元素选不选都不重要了，当前问题的解都为true。如果之前的数不能，你又没有选当前元素，那就是false。
但如果选呢，这时候就要考虑容量的问题了，举个例子，现在需要选出一部分数，使得和为十五 。如果第六个元素值为五，这时我们选择了第六个元素，那么前五个元素需要满足什么条件才能使得前六个元素中选出的一部分数的和能为十五呢？
仔细想想，就能得出结论，前五个数中必须能选出一部分数使得和为十，加上之前已经选择了的第六个元素的值五。才能使得从前六个数中能选出部分数使得和为十五 。想明白这点，你就知道dp为什么会那样定义了。
定义为二维数组，就是要求出前n个数中选择部分数的和能得到的所有和的可能。举个例子，前五个数中，选出部分数的和能否得到0,1,2,3,4,5,6,7,8,9 。因为dp数组的值可能会用到他们的值。当然在这个问题中这个范围是受限的。
我们推导出状态转移方程：
图片来自力扣
补充一点，如果当前元素大于 j 的值，那当前元素只有一种选择，那就是不选。因为装不下。
2.代码实现
bool canPartition(vector<int>& nums) {
int n = nums.size();
if (n < 2) {
return false;
}
int sum = accumulate(nums.begin(), nums.end(), 0);
int maxNum = *max_element(nums.begin(), nums.end());
if (sum & 1) {
return false;
}
int target = sum / 2;
if (maxNum > target) {
return false;
}
vector<vector<int>> dp(n,vector<int>(target+1,0));
for(int count=0;count<n;++count){
dp[count][0]=true;
}
dp[0][nums[0]]=true;
for(int count=1;count<n;++count){
int tmp=nums[count];
for(int count1=1;count1<=target;++count1){
if(tmp>count1){
dp[count][count1]=dp[count-1][count1];
}
else{
dp[count][count1]=dp[count-1][count1] | dp[count-1][count1-tmp];
}
}
}
return dp[n-1][target];
}
上述代码还可以优化空间，变为使用一维数组。
bool canPartition(vector<int>& nums) {
int n = nums.size();
if (n < 2) {
return false;
}
int sum = accumulate(nums.begin(), nums.end(), 0);
int maxNum = *max_element(nums.begin(), nums.end());
if (sum & 1) {
return false;
}
int target = sum / 2;
if (maxNum > target) {
return false;
}
vector<int> dp(target+1,0);
dp[0]=true;
for(int count=0;count<n;++count){
int tmp=nums[count];
for(int count1=target;count1>=tmp;--count1){
dp[count1] |=dp[count1-tmp];
}
}
return dp[target];
}
这种优化其实是从观察代码执行步骤得出的，并不是对问题解法的优化，然后再得出的代码。
需要注意的是当前dp数组的值取决于之前的dp数组的值，所以使用一维数组需要从后往前遍历，以免覆盖之前的值，造成结果的错误。
5.总结
对于计数，求和的问题，状态转移方程的一般形式是相加；对于求最值问题，状态转移方程的一般形式是从两个状态中取最大或最小的那个；对于求存在性问题，状态转移方程的一般形式是直接赋值。
其实动态规划的题目有很多类型，还是需要具体问题具体分析，不能一味的套公式，以上只是对常见的动态规划问题做的一些总结，希望有帮助。