一、动态规划
动态规划与分治方法类似，都是通过子问题的组合来求解原问题的，但是分治法是划分为互不干扰的子问题而动态规划划分的子问题往往都是具有重叠效应的，前一个子问题会影响后一个子问题。
动态规划题目种类：
-
计数
有多少种方式走到右下角
有多少种方法选出k个数使得和是sum -
求最大最小值
从左上角走到右下角路径的最大数字和
最长上升序列长度 -
求存在性
取石子游戏，先手是否必胜
能不能选出k个数使得和是sum
对于这种十分抽象的算法介绍，我的一贯学习方法是学例题，从例题中总结一般的解题思路（说的这么高大上，其实就是模仿）。
二、动态规划例题
首先讲解一下动态规划算法的一般解题思路:
- 确定状态
简单来说就是解动态规划题一般而言要定义一个数组f，确定状态就是确定数组中的每个元素f[i]或f[i][j]的含义，即f[i]或者f[i][j]代表什么。
确认状态需要两个意识：1.最后一步 2.子问题 - 转移方程(核心)
- 初始条件和边界
- 计算顺序：f[0]、f[1]、f[2]、…
或者你现在看着这个解题步骤还是很迷茫，没关系，这很正常，下面我们结合例题进一步讲解，相信看完例题后你能有更深一步的理解。
1.最少硬币问题（最小）
题目大意：你有三种硬币，币值分别为2、5、7，且每种硬币的数量足够多，此时你想买一本27元的书，问：怎么样的硬币组合需要的硬币个数最少，且不需要对方找钱。
第一步，确定状态：
首先是最后一步，假设最后一步拿出的硬币的币值为mk,那么还剩27-mk的总价值，需要的总的硬币数为f(27-mk)+1（定义函数f(x)为价值为x时最少需要的硬币个数），此时子问题就显而易见了，即f(27-mk)：总价值为27-mk时最少需要的硬币个数。那么通过最后一步的意识得出了动态规划问题中的子问题，这个子问题通过相同的想法得到下一个子问题…。此外根据函数f我们定义数组f，f[i]的含义就为总价值为i时最少需要的硬币个数。
第二步，转移方程：
显然最后一步的选择有三种，即拿出币值为2的硬币、拿出币值为5的硬币、拿出币值为7的硬币。那么整体的转移方程如下：
f(27)=min{f(27-2)+1,f(27-5)+1,f(27-7)+1}
转移方程既然已知，我们脑海中就很容易想到递归的想法：
int f(int X){
//f(X)=最少用多少枚硬币拼出X
if(X==0) return 0; //0元只需要0枚硬币
int res=INT_MAX; //初始化用无穷大
if(X>=2){
//最后一枚硬币为2元
res=min(f(X-2)+1,res);
}
if(X>=5){
//最后一枚硬币为5元
res=min(f(X-5)+1,res);
}
if(X>=7){
//最后一枚硬币为7元
res=min(f(X-7)+1,res);
}
return res;
}
但是大多数情况下，递归的时间复杂度很高，不可取。因此我们考虑采用逐一计算的方法，定义数组f，f[i]的含义就为总价值为i时最少需要的硬币个数。从f[0]一直计算到f[27]那么结果就出来了。
第三步、初始条件和边界条件：f[0]=0,如果不能拼凑Y则f[Y]=正无穷。
第四步、计算顺序：f[0]、f[1]、f[2]…
代码如下：
//硬币最少问题
//有的硬度的币值为：2，5，7
//币值为2，5，7的三种硬币，买总价值为m的物品，怎么组合硬币的个数最少
#include<iostream>
#include<vector>
using namespace std;
int main()
{
//第一步：确定状态，这个问题中确定状态分为两件事：1.最后一步（最优问题中使用的最后一枚硬币）、2.子问题（转化为求解m-mk）
//第二步：转移方程f[x]=min{f[x-2]+1,f[x-5]+1,f[x-7]+1}
//第三步：初始条件和边界条件，f[0]=0,如果不能拼凑Y则f[Y]=正无穷
//第四步：计算顺序：f[0]、f[1]、f[2]...
vector<int> A = {
2,5,7 }; //价格表
int m=27; //总价值
//定义一个数组
vector<int> f(m + 1);
int n = A.size();
f[0] = 0;
//f[0],f[1],f[2]...
for (int i = 1; i <= m; i++)
{
f[i] = INT_MAX;
//lost coin A[j]
//f[i]=min(f[i-A[0]]+1,f[i])
for (int j = 0; j < n; j++)
{
if (i - A[j] >= 0 && f[i-A[j]]!=INT_MAX) {
f[i] = min(f[i - A[j]] + 1, f[i]);
}
}
//输出f[]
cout << "f[" << i << "]:" << f[i] << endl;
}
if (f[m] == INT_MAX) {
f[m] = -1;
}
cout << f[m] << endl;
return 0;
}
2.钢条切割问题（最大）
题目大意：当有一段长度为i的钢条，怎样切割卖出的钱最多，价格表如下：
| 长度 i | 1 2 3 4 5 6 7 8 9 10 |
|---|---|
| 价格p | 1 5 8 9 10 17 17 20 24 30 |
第一步，确认状态：
首先是最后一步，长度为M的钢条最后切割的长度为mk，那么剩余的长度为i-mk，那么能获得的总价值为f(i-mk)(注：定义函数f(x)为长度为x的钢条经过切割能获得的最大价值)+f(mk)。子问题可得。
第二步、转移方程：
显然最后一步的选择有十种，1-10，那么转移方程如下：
当i<=10可以切也可以不切,f[i]=max{p[i],f[i-1]+f[1],f[i-2]+f[2],…,f[i-10]+f[10]}
当i>10必须切,f[i]=max{f[i-1]+f[1],f[i-2]+f[2],…,f[i-10]+f[10]}
第三步、初始条件和边界条件：f[0]=0
第四步、计算顺序：f[0]、f[1]、f[2]…
//2021.3.6
//钢条切割问题
#include<iostream>
#include<vector>
using namespace std;
int main()
{
vector<int> p = {
0,1,5,8,9,10,17,17,20,24,30 }; //长度为i时对应的价格为p[i]
int m=34; //总长
vector<int> f(m + 1); //记录从长为0到长为m钢条最大能买的钱
f[0] = 0; //初始条件
//计算f[1],f[2],...,f[m]
for (int i = 1; i <= m; i++)
{
if (i >= 1 && i <= 10)
{
f[i] = p[i];
}
//当i<=10,f[i]=max{p[i],f[i-1]+f[1],f[i-2]+f[2],...,f[i-10]+f[10]}
//当i>10,f[i]=max{0,f[i-1]+f[1],f[i-2]+f[2],...,f[i-10]+f[10]}
for (int j = 1; j <= 10; j++)
{
if (i - j > 0) {
f[i] = max(f[i], f[i - j] + f[j]);
}
}
}
cout << f[m] << endl;
return 0;
}
3.不同路径问题（计数2）
题目大意：
第一步，确认状态：
首先是最后一步，到最后一点的finish有两种可能，从上面下来的即从[m-2][n-1]→[m-1][n-1] (均采用数组表示法，3行7列的数组最后一个元素小标为[2][6])，或者从右边过来的即从[m-1][n-2]→[m-1][n-1]，定义函数f(i)(j)为起点[0][0]到[i][j]的路径的数量，子问题就为求f(i)(j)。
第二步、转移方程：
f[i][j]=f[i-1][j]+f[i][j-1]
第三步、初始条件和边界条件：f[0][j]=1,f[i][0]=0
第四步、计算顺序：f[1][1]、f[1][2]、f[1][3]…f[2][1]、f[2][2]…
//2021.3.7
//机器人路径问题
#include<iostream>
#include<vector>
using namespace std;
int main()
{
int m = 3; //3行
int n = 7; //7列
vector<vector<int>> f(m);
for (int i = 0; i < m; i++)
{
f[i].resize(n);
}
//初始化第一行
for (int j = 0; j < n; j++)
{
f[0][j] = 1;
}
//初始化第一列
for (int i = 0; i < m; i++)
{
f[i][0] = 1;
}
for (int i = 1; i < m; i++)
{
for (int j = 1; j < n; j++)
{
f[i][j] = f[i][j - 1] + f[i - 1][j];
}
}
cout << f[m - 1][n - 1] << endl;
return 0;
}
4.青蛙过河（存在性动态规划）
题目大意：
第一步，确认状态：
首先是最后一步，当青蛙在石头n-1上，可能是从石头i跳过的（i<n-1）,子问题：求是否能从石头0跳到石头i上，定义数组f，f[i]为从石头0跳到石头i上的可能性，为0则不能，为1则代表能。
第二步、转移方程：
f[j]=(f[i] AND i+a[j]>=j) (0<=i<j,i从0枚举到j，存在满足上式的i就把f[j]赋值为1，代表可以从0跳到j)
第三步、初始条件和边界条件:f[0]=1
第四步、计算顺序：f[0],f[1],f[2],…
#include<iostream>
#include<vector>
using namespace std;
int main()
{
vector<int> a = {
3,2,1,0,4}; //
int m = a.size();
vector<int> f(m);
f[0] = 1;
for (int i = 1; i < m; i++)
{
f[i] = 0;
for (int t = 0; t < i; t++)
{
if (f[t] == 1 && t + a[t] == i)
{
f[i] = 1;
}
}
}
cout << f[m - 1] << endl;
return 0;
}
几种类型的动态规划题都在这了，如果对你有用的画不妨点个赞支持一下吧。