基础DP（状态转移和递推）
1.硬币问题
有多个不同面值的硬币，输入最少硬币组合。
这里要是用贪心，所得组合和实际可能不符合。
利用dp法，代码如下：
#include<bits/stdc++.h>
using namespace std;
const int MONEY=1001; //定义最大金额
const int VALUE=5; //5种硬币
int type[VALUE]={ 1,5,10,25,50}; //5种面值
int Min[MONEY]; //每个金额对应最少的硬币数量
void solve(){
for(int k=0;k<MONEY;k++) //初始值为无穷大
Min[k]=INT_MAX;
Min[0]=0;
for(int j=0;j<VALUE;j++)
for(int i=type[j];i<MONEY;i++)
Min[i]=min(Min[i],Min[i-type[j]]+1); //递推式
}
int main(){
int s;
solve(); //提前计算出所有金额对应的最少硬币数量。打表
while(cin>>s)
cout<<Min[s]<<endl;
return 0;
}
拓展问题：要求打印最少硬币的组合。
解决方法：增加一个记录表Min_path[i]，记录金额i需要的最后一个硬币。利用Min_path[]逐步倒推，就能得到所有的硬币。
如：
Min_path[6]=5：最后一个硬币是5元的；
Min_path[6-5]=1：1元硬币；
Min_path[1-1]=0：结束；
代码如下：
#include<bits/stdc++.h>
using namespace std;
const int MONEY=1001; //定义最大金额
const int VALUE=5; //5种硬币
int type[VALUE]={ 1,5,10,25,50}; //5种面值
int Min[MONEY]; //每个金额对应最少的硬币数量
int Min_path[MONEY]={ 0}; //记录最小硬币的路径
void solve(){
for(int k=0;k<MONEY;k++)
Min[k]=INT_MAX;
Min[0]=0;
for(int j=0;j<VALUE;j++)
for(int i=type[j];i<MONEY;i++)
if(Min[i]>Min[i-type[j]]+1){
Min_path[i]=type[j]; //在每个金额上记录路径，即某个硬币的面值
Min[i]=Min[i-type[j]]+1; //递推式
}
}
void print_ans(int *Min_path,int s){ //打印硬币组合
while(s){
cout<<Min_path[s]<<" ";
s=s-Min_path[s];
}
}
int main(){
int s;
solve();
while(cin>>s){
cout<<Min[s]<<endl; //输出最少硬币个数
print_ans(Min_path,s); //打印硬币组合
}
return 0;
}
拓展问题：硬币组合方案有几种
代码如下：
#include<bits/stdc++.h>
using namespace std;
const int COIN=101; //题目要求不超过100个硬币
const int MONEY=251; //题目给定的钱数不超过250
int dp[MONEY][COIN]={ 0}; // DP转移矩阵
int type[5]={ 1,5,10,25,50}; //5种面值
void solve(){ // DP
dp[0][0]=1;
for(int i=0;i<5;i++)
for(int j=1;j<COIN;j++)
for(int k=type[i];k<MONEY;k++)
dp[k][j]+=dp[k-type[i]][j-1];
}
int main(){
int s;
int ans[MONEY]={ 0};
solve(); //用DP计算完整的转移矩阵
for(int i=0;i<MONEY;i++) //对每个金额，计算有多少种组合方案。打表
for(int j=0;j<COIN;j++) //从0开始，注意 dp[0][0]=1
ans[i]+=dp[i][j];
while(cin>>s)
cout<<ans[s]<<endl;
return 0;
}
2.0/1背包问题
用dp[i][j]数组，表示将前i个物品放入容量为j的背包中产生的价值。
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。
接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤1000
0<vi,wi≤1000
输入样例
4 5
1 2
2 4
3 4
4 5
输出样例：
8
代码如下：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
typedef struct{
int v;
int w;
}Node;
int dp[1005][1005];
int main()
{
int N,V;
scanf("%d%d",&N,&V);
Node* node=new Node[N+1];
for(int i=1;i<=N;i++)
scanf("%d%d",&node[i].v,&node[i].w);
for(int i=1;i<=N;i++){
for(int j=1;j<=V;j++){
if(node[i].v>j)
dp[i][j]=dp[i-1][j];
else
dp[i][j]=max(dp[i-1][j-node[i].v]+node[i].w,dp[i-1][j]);
}
}
printf("%d\n",dp[N][V]);
}
动态规划法的设计思想：
如果各个子问题的不是独立的，如果能够保存已经解决的子问题的答案，而在需要的时候再找出已求得的答案，这样就可以避免大量的重复计算。‘
基本思路是，用一个表记录所有已解决的子问题的答案，不管该问题以后是否被用到，只要它被计算过，就将其结果填入表中。
3.完全背包问题
有 N 种物品和一个容量是 V 的背包，每种物品都有无限件可用。
第 i 种物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。
接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 种物品的体积和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤1000
0<vi,wi≤1000
输入样例
4 5
1 2
2 4
3 4
4 5
输出样例：
10
直接上一段代码：
#include<bits/stdc++.h>
using namespace std;
typedef struct{
int v,w;
}Node;
int dp[1005][1005];
int main(){
int N,V;
scanf("%d%d",&N,&V);
Node* node=new Node[N+1];
for(int i=1;i<=N;i++)scanf("%d%d",&node[i].v,&node[i].w);
for(int i=1;i<=N;i++)
for(int j=0;j<=V;j++)
for(int k=0;k*node[i].v<=j;k++)
dp[i][j]=max(dp[i][j],dp[i-1][j-k*node[i].v]+k*node[i].w);
printf("%d\n",dp[N][V]);
}
这个代码和0/1背包有些相似，这里求解dp数组时，用3个for循环，遍历前i个物品在背包容量为j的背包中产生的最大价值，方法为：
取定第i个物品，直接循环确定从0最大的k个i物品能产生的最大价值。可以理解为：装入k个i物品，相当于将前i-1个物品选定最大价值装入容量为j-knode[i].v的包中，那么这样做的价值为dp[i-1][j-knode[i].v]+k*node[i].w，和原始的dp[i][j]不断比较，逐渐选择出最大价值的dp[i][j]
理解完全背包问题时，可以和0/1背包做比较，加深理解。
但是这题如果是这样做的话，显得太过暴力，事实上，这样提交上去是会给超时的！
那么接下来，我们需要对这个问题做个优化：
首先了解dp更新时的内部关系：
dp[i][j]=max(dp[i-1][j],dp[i-1][j-v]+w,dp[i-1][j-2v]+2w+dp[i-1][j-3v]+3w+…)
递推下去
dp[i][j – v] = max ( ,dp[i-1][j-v],dp[i-1][j-2v]+w+dp[i-1][j-3v]+2*w)；
递推得出：dp[i][j]=max(dp[i-1][j],dp[i][j-v]+w);
有了上面的递推关系式，可以将代码优化为：
for(int i=1;i<=N;i++)
for(int j=0;j<=V;j++)
if(j-node[i].v>=0)
dp[i][j]=max(dp[i][j],dp[i][j-node[i].v]+ndoe[i].w);
else dp[i][j]=dp[i-1][j];
至此，完全背包优化代码如下：
#include<bits/stdc++.h>
using namespace std;
typedef struct{
int v,w;
}Node;
int dp[1005][1005];
int main(){
int N,V;
scanf("%d%d",&N,&V);
Node* node=new Node[N+1];
for(int i=1;i<=N;i++)scanf("%d%d",&node[i].v,&node[i].w);
for(int i=1;i<=N;i++)
for(int j=0;j<=V;j++)
if(j-node[i].v>=0)
dp[i][j]=max(dp[i-1][j],dp[i][j-node[i].v]+node[i].w);
else dp[i][j]=dp[i-1][j];
printf("%d\n",dp[N][V]);
}
4.最长公共子序列
给定两个长度分别为 N 和 M 的字符串 A 和 B，求既是 A 的子序列又是 B 的子序列的字符串长度最长是多少。
输入格式
第一行包含两个整数 N 和 M。
第二行包含一个长度为 N 的字符串，表示字符串 A。
第三行包含一个长度为 M 的字符串，表示字符串 B。
字符串均由小写字母构成。
输出格式
输出一个整数，表示最大长度。
数据范围
1≤N,M≤1000
输入样例：
4 5
acbd
abedc
分析：
分别遍历两个序列。
若Ai=Bj，求最长公共子序列的长度，则只需要求A的前i-1个和B的前j-1个公共子序列的长度，然后再加1即可。即：
dp[i][j]=dp[i-1][j-1]+1;
若Ai!=Bj，求最长公共子序列的长度，只有两种可能，一种是A的前i个和B的前j-1的最长公共子序列长度，另一种是A的前i-1个和B的前j个的最长公共子序列长度。即：
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
知晓了动态方程，代码就能很容易写出：
#include<bits/stdc++.h>
using namespace std;
int num[1005][1005];
int main(){
int n,m;
string a,b;
scanf("%d%d",&n,&m);
cin>>a;
cin>>b;
memset(num,0,sizeof(num));
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i-1]==b[j-1])num[i][j]=num[i-1][j-1]+1;
else
num[i][j]=max(num[i-1][j],num[i][j-1]);
}
}
printf("%d\n",num[n][m]);
}
5.最长递增子序列（LIS问题）
给定一个长度为 N 的数列，求数值严格单调递增的子序列的长度最长是多少。
输入格式
第一行包含整数 N。
第二行包含 N 个整数，表示完整序列。
输出格式
输出一个整数，表示最大长度。
数据范围
1≤N≤1000，
−109≤数列中的数≤109
输入样例：
7
3 1 2 1 8 5 6
输出样例：
4
分析：
用双重循环，第一层循环遍历这个数列，第二个循环借助在第一层循环遍历到的数列下标i，再次遍历数组从0到i-1，如果遍历的数列num[i]>num[j]，那么最长递增长度要么是以遍历到j的最长长度+1，要么就是原先计算出来的最长长度（一开始每个第一层循环开始时元素的最长递增长度都设置为1），接着再用一个元素记录最长的长度即可。
这样做的复杂度为O(n^2)。
代码如下：
#include<bits/stdc++.h>
using namespace std;
int main(){
int N;
scanf("%d",&N);
int* num=new int[N];
int* dp=new int[N];
int len=1;
for(int i=0;i<N;i++)scanf("%d",&num[i]);
for(int i=0;i<N;i++){
dp[i]=1;
for(int j=0;j<i;j++)
if(num[i]>num[j])
dp[i]=max(dp[i],dp[j]+1);
len=max(len,dp[i]);
}
printf("%d\n",len);
}
该题可以用更高效的算法，利用dp以及二分法。dp表示规则为：
dp[i]表示长度为i的递增子序列中最后一个元素最小的值。
状态计算：对所有num[i]，如果大于dp[cnt-1]，(下标从0开始，cnt长度的最长上升子序列，末尾最小的数字)，那就cnt++，使得最长上升序列长度+1，当前末尾最小元素为num[i]；若num[i]小于等于dp[cnt-1],说明不会更新当前的长度，但之前末尾的最小元素要发生变化，找到第一个 大于或等于 (这里不能是大于) num[i]，更新以那时候末尾的最小元素。
dp[i]一定是一个单调递增的数组，所以可以用二分法查找，复杂度为O(nlogn)
代码如下：
#include<bits/stdc++.h>
using namespace std;
int main(){
int N,cnt=0;
scanf("%d",&N);
int* num=new int[N];
int* dp=new int[N];
for(int i=0;i<N;i++)scanf("%d",&num[i]);
dp[cnt++]=num[0];
for(int i=1;i<N;i++){
if(num[i]>dp[cnt-1])dp[cnt++]=num[i];
else{
int l=0,r=cnt-1;
while(l<r){
int mid=(l+r)>>1;
if(dp[mid]>=num[i])r=mid;
else l=mid+1;
}
dp[r]=num[i];
}
}
printf("%d\n",cnt);
}
递推和记忆化搜索
前面dp的状态转移，都是用递推的方法。
有另一种方法，逻辑上的理解更加直接，就是“递归+记忆化搜索”实现递归。
经典题：The Triangle
给定一个n层的三角形数塔，从顶部第一个数往下走，每层经过一个数字，直到最底层。只能走斜下方的左边一个数或右边一个数。问所有可能走到的路径最大的数字和为多少？
分析：
本题如果按“从顶往下”的计算方法，有2^n个路径，导致TLE。
可以使用递推，即从底往上计算，对数塔上的每个点记录状态，dp[i][j]记录从第i层第j个数开始往下走的数字和，每个节点算一次，复杂度O(n^2)。
dp的另一种写法：递归+记忆化搜索：
首先，写递归程序，暴力搜索所有2^n个路径
int dfs(int i,int j){
if(i==n)
return a[i][j];//递归边界，到达最后一行，返回
return dp[i][j]=max(dfs(i+1,j),dfs(i+1,j+1))+a[i][j];
//从左边走上来，或者从右边走上来，取其中大的。
}
递归的优化：记忆化搜索
递归时，可以避免大量的重复计算，如下图：
观察第3层的中间数“1”，从第二层的“3”往下走会经过它，从第二层的“8”往下走也会经过它，那么就重复计算了1开始的递归，只要能避免这些重复计算，就能优化。
int dfs(int i,int j){
if(i==n)
return a[i][j];
if(dp[i][j]>=0)return dp[i][j];//记忆
return dp[i][j]=max(dfs(i+1,j),dfs(i+1,j+1))+a[i][j];
}
区间dp
步骤：（1）先在小区间进行dp得到最优解；
（2）合并小区间的最优解，求大区间的最优解
经典题1：石子合并
设有 N 堆石子排成一排，其编号为 1，2，3，…，N。
每堆石子有一定的质量，可以用一个整数来描述，现在要将这 N 堆石子合并成为一堆。
每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同。
例如有 4 堆石子分别为 1 3 5 2， 我们可以先合并 1、2 堆，代价为 4，得到 4 5 2， 又合并 1，2 堆，代价为 9，得到 9 2 ，再合并得到 11，总代价为 4+9+11=24；
如果第二步是先合并 2，3 堆，则代价为 7，得到 4 7，最后一次合并代价为 11，总代价为 4+7+11=22。
问题是：找出一种合理的方法，使总的代价最小，输出最小代价。
输入格式
第一行一个数 N 表示石子的堆数 N。
第二行 N 个数，表示每堆石子的质量(均不超过 1000)。
输出格式
输出一个整数，表示最小代价。
数据范围
1≤N≤300
输入样例：
4
1 3 5 2
输出样例：
22
分析：
核心：最后一次合并一定是左边连续的一部分和右边连续的一部分进行合并
状态表示：dp[i][j]表示把第i堆到第j堆合并的方案集合中的最小代价。
区间dp的常用模板：
第一维枚举区间长度，从1到n-1；第二维枚举起点i，从i到n-len；则终点就为j=i+len（自动生成）
代码如下：
#include<bits/stdc++.h>
using namespace std;
const int INF=1<<30;
const int N=305;
int sum[N],n;
int Minval(){
int dp[N][N];
for(int i=1;i<=n;i++)
dp[i][i]=0;
for(int len=1;len<n;len++) //len是i和j之间的距离
for(int i=1;i<=n-len;i++){ //从第i堆开始
int j=i+len; //自动得到右端点
dp[i][j]=INF;
for(int k=i;k<j;k++) //i和j之间，用k进行分割
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);
}
return dp[1][n];
}
int main(){
cin>>n;
sum[0]=0;
for(int i=1;i<=n;i++){
int x;
cin>>x;
sum[i]=sum[i-1]+x; //sum[i,j]的值等于 sum[j]-sum[i-1]
}
cout<<Minval()<<endl;
return 0;
}
经典题2：回文串（暂略）
树形dp
在树这种数据结构上进行的dp：给出一棵树，要求以最少的代价（或取得最大收益）完成给定的操作。
在树上做动态规划很适合，因为树本身有“子结构”性质，具有递归性，符合dp的性质。