DP初识
哪些题目适合用DP算法解决？
1.满足最优子结构
大问题可以由小问题推出，大问题与小问题求解思路一致（相当于递归思路）
2.满足无后效型
一旦f(n)确定，后续我们直接调用它的值就可以，而不用关心它是怎样过来的
例：
（1）计数：
–有多少种方式走到右下角
–有多少种方法选出k个数使得和是sum
（2）求最大最小值：
–从左上角走到右下角路径的最大数字和
–最长上升子序列长度
（3）求存在性：
–取石子游戏，先手是否必胜
–能不能选出k个数使得和是sum
DP关键步骤
1.设计好状态
解动态规划的时候需要开一个数组，想办法把当前局面给表达出来，写出f(x)，想明白数组的每个元素f[i]或者f[i][j]代表什么
确定状态需要两个意识：
最后一步：单独将最后一步提出来
子问题： 最后一步提出来后剩下的一个规模较小的子问题
然后根据原问题和子问题的公共部分写出状态数组f[x]代表的含义
2.设置好状态转移方程
可以从两个方面考虑，我从哪里来，或者我到哪里去
DP典型基础案例
案例一、最长递增子序列（LIS）问题
问题描述：
求一个序列的最长递增子序列，这样的子序列是允许中间越过一些字符的，即留“空”。
例如：4 2 3 1 5 的最长递增子序列为 2 3 5，长度为 3 。
解法：
设计状态
记f(x)为以a[x]结尾的LIS长度，那么LIS=max{f(x)}.
数据： 1 5 3 4 8
索引： 1 2 3 4 5
a[x] : a[1] a[2] a[3] a[4] a[5]
推导f(x)
注意初始情况和边界条件
考虑比x小的每一个p，如果a[x]>a[p],那么f(x)=f( p )+1;
状态转移方程
f(x)=max{f( p )}+1;
找f[x]与前面数组元素的关系，递归是从后往前推，但是用递归会进行很多重复的操作，如果不用数组记忆，数据规模很大时会运行超时，所以直接用一个数组来存储当前元素的最长子序列长度
具体实现：
// 用数组代替每次重复递归计算
#include<iostream>
#include<algorithm>
using namespace std;
int *arr;
int *dp; //动态规划的状态数组
void test(int n)
{
dp[0]=1; //设置初始状态
for(int i=1;i<n;i++)
{
int max=1,now=1;
for(int j=i-1;j>=0;j--)
{
if(arr[j]<arr[i])
{
now=dp[j]+1; //搜索到比当前数据小的，表示可以从这个点跳到当前数据，增长递增序列的长度
if(now>max) max=now;
}
}
dp[i]=max; //存储到当前数据的最长递增序列的长度
}
cout<<dp[n-1];
}
int main(){
int n;
cin>>n;
arr = new int[n];
dp = new int[n];
for (int i = 0; i < n; i++)
{
cin >> arr[i];
}
test(n);
delete[] arr;
delete[] dp;
return 0;
}
案例二、硬币面值和
问题描述：
你有三种硬币，分别面值2元、5元、7元，每种硬币都有足够多，买一本书需要27元，如何用最少硬币组合正好付清，不需要对方找钱
DP解决方法：
1.分辨出这是求最大最小值动态规划问题
2.设计状态
最后一步：
虽然我们不知道最优策略是什么，但是最优策略肯定是K枚硬币a1,a2…ak面值加起来是27，所以一定有一枚最后的硬币ak，出掉这枚硬币，前面硬币的面值加起来是27-ak；
我们不用关心前面的k-1枚硬币是怎么拼出27-ak的，我们甚至不知道ak和k，但是我们确定前面的硬币拼出了27-ak，并且拼出27-ak的硬币数一定要最少，否则就不是最优策略了
所以我们就要求：最少用多少枚银币可以拼出27-ak
原问题是：最少用多少枚硬币拼出27
则设置状态f[X]= 最少用多少枚硬币拼出X
3.状态转移方程
对于任意X，f[X] = min{ f[X-2] +1,f[X-5] +1, f[X-7] +1 }
4.初始条件和边界情况
(1) 下标越界： X-2、X-5、X-7小于0
如果不能拼出X，就定义f[X] = 正无穷(一个很大的数)
例如 f [-1] = f[-2] = 正无穷
所以f [ 1 ] =min{f [-1 ] +1,f[ -4 ] +1,f[ -6 ]+1 } =正无穷，表示拼不出来1
(2)什么时候停下来
初始条件f [ 0 ] =0 ,这样f[1] 、f[2]、f[3]…f[27] 都能表达出来了
5.计算顺序
f[1] 、f[2] 、f[3] 、、、、、f[27
]
// 用数组代替每次重复递归计算
#include<bits/stdc++.h>
using namespace std;
#define MAX 100000
int min(int a,int b,int c)
{
int t=a;
if(t>b) t=b;
if(t>c) t=c;
return t;
}
int main(){
int n=28;
int dp[28];
// 状态 ：dp[x]=min[dp[x-2]+1,dp[x-5]+1,dp[x-7]+1];
dp[0]=0;
for(int i=1;i<n;i++)
{
int a,b,c;
if(i-2>=0) a=dp[i-2]+1;
else a=MAX;
if(i-5>=0) b=dp[i-5]+1;
else b=MAX;
if(i-7>=0) c=dp[i-7]+1;
else c=MAX;
dp[i]=min(a,b,c);
}
for(int i=1;i<n;i++)
{
if(dp[i]==MAX) cout<<"不能得到 "<<i<<endl;
else cout<<i<<" 最少需要 "<<dp[i]<<" 步"<<endl;
}
return 0;
}
案例三、Unique Paths
问题描述：
给定m行n列的网络，有一个机器人从左上角(0,0)出发，每一步可以向下或者向右走一步
问有多少种不同的方式走到右下角
DP解决方法：
1.计数型动态规划
2.确定状态
最后一步：无论机器人用何种方式到达右下角，总有最后挪动的一步：向右或者向下
右下角坐标设为(m-1,n-1)
前一步机器人一定是在(m-2,n-1) 或者(m-1,n-2)
子问题：
问题转化为机器人有多少种方式从左上角走到(m-2,n-1)和(m-1,n-2)
原问题 有多少种方式从左上角走到(m-1,n-1)
设置状态：设f[i][j]为机器人有多少种方式从左上角走到(i,j)
3.状态转移方程
对于任意i、j ，f[i][j] = f[i-1][j] + f[i][j-1]
4. 初始条件 : f[0][0] = 1,因为机器人只有一种方式到左上角
边界情况 ： i=0或j=0,则前一步只能有一个方向过来–> f[i][j] =1
5.计算顺序： 先行再列，保证此时需要的两个方向的路径已经求出来了
#include<bits/stdc++.h>
using namespace std;
int main()
{
int m,n;
cin>>m>>n;
int dp[m][n];
dp[0][0]=1;
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
if(i==0||j==0) dp[i][j]=1;
else
{
dp[i][j]=dp[i-1][j]+dp[i][j-1];
}
}
}
cout<<dp[m-1][n-1];
return 0;
}