一 经典线性dp
1.最大和连续子序列
https://www.acwing.com/problem/content/3396/
dp[i]:前i个且结尾为a[i]的最大连续子序列和
dp[i]=max(dp[i−1]+a[i],a[i])
2.最大和子序列
贪心:把大于0的都选出来
3.最长递增子序列
https://www.acwing.com/problem/content/897/
dp[i]:前i个且结尾为a[i]的最长递增子序列
预处理:dp[i]=1
dp[i]=max(dp[i],dp[j]+(a[i]>a[j]))(j<i)
4.最大上升子序列和
https://www.acwing.com/problem/content/1018/
dp[i]:前i个且结尾为a[i]的最长递增子序列
sum[i]:前i个且结尾为a[i]的最长递增子序列和
预处理:dp[i]=1,sum[i]=a[i]
dp[i]=max(dp[i],dp[j]+(a[i]>a[j]))(j<i)
sum[i]=max(sum[i],sum[j]+a[i])(a[i]>a[j])and(dp[j]+1>dp[i])
4.最大乘积连续子序列
https://ac.nowcoder.com/acm/contest/53918/K
dp1[i]:前i个的最大乘积连续子序列
dp2[i]:前i个的最小乘积连续子序列
预处理:dp1[0]=dp2[0]=1;
dp1[i]=max(max(dp1[i−1]∗a[i],a[i]),dp2[i−1]∗a[i]);
dp2[i]=min(min(dp2[i−1]∗a[i],a[i]),dp1[i−1]∗a[i]);
5.最大乘积子序列
贪心:把所有正数,再选择偶数个负数，特殊情况只有一个负数。或者0的一些特殊情况。
6.最长回文子序列
dp[i][j]:i到j中最长回文序列的长度
循环变量: i:n-1~0 j:i+1~n-1
预处理:dp[i][i]=1
dp[i][j]=dp[i+1][j−1]+2(s[i]==s[j])
dp[i][j]=max(dp[i+1][j],dp[i][j−1])(s[i]!=s[j])
7.最长回文子串
贪心:枚举中心,扩展半径
dp:
dp[i][j]:i到j中最长回文子串的长度
dp[i][j]=dp[i+1][j−1]+2，(s[i]=s[j])and(dp[i+1][j−1]=j−i−1)
dp[i][j]=max(dp[i+1][j],dp[i][j−1])，else
8.最长公共子序列
dp[i][j]: a[1~i]和b[1~j]中的最长公共子序列长度
预处理:dp[i][i]=0
dp[i][j]=dp[i−1][j−1]+1，(a[i]==b[j])
dp[i][j]=max(dp[i−1][j],dp[i][j−1])，else
二 背包问题
1.01背包问题
题意:有 N 件物品和一个容量是 V的背包。每件物品只能使用一次。第 i件物品的体积是 vi，价值是 wi。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。
dp[i][j]:前 i 个物品，背包容量 j 下的最优解（最大价值)。
循环变量:i:1−Nj，0−V
dp[i][j]=dp[i−1][j]，j<v[i]
dp[i][j]=max(dp[i−1][j]，dp[i−1][j−v[i]]+w[i])，else
2.完全背包问题
题意:有 N 件物品和一个容量是 V的背包。每种物品都有无限件可用。第 i件物品的体积是 vi，价值是 wi。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。
dp[i][j]:前 i 个物品，背包容量 j 下的最优解（最大价值)。
循环变量:i:1−Nj，0−V
dp[i][j]=dp[i−1][j]，j<v[i]
dp[i][j]=max(dp[i−1][j],dp[i][j−v[i]]+w[i])，else
3.多重背包问题
题意:有 N 件物品和一个容量是 V的背包。第 i 种物品最多有 si 件。第 i件物品的体积是 vi，价值是 wi。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。
dp[i][j]:前 i 个物品，背包容量 j 下的最优解（最大价值)。
循环变量:i:1−Nj，0−V，k:0−s[i]
dp[i][j]=max(dp[i][j],dp[i−1][j−k∗v[i]]+k∗w[i])，(k∗v[i]<=j)
4.分组背包问题
题意:有 N 组物品和一个容量是 V 的背包。每组物品有若干个，同一组内的物品最多只能选一个。每件物品的体积是 vij，价值是 wij，其中 i 是组号，j 是组内编号。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。
dp[i][j]:前 i 组物品，背包容量 j 下的最优解（最大价值)。
循环变量:i:1−N，j:0−V，k:1−s[i]
预处理:dp[i][j]=dp[i−1][j] or 不进行预处理 k:0−s[i]
dp[i][j]=max(dp[i][j],dp[i−1][j−v[i][k]]+w[i][k])，(j−v[i][k]>=0)
三 区间dp
1.石子合并
设有 N 堆石子排成一排，其编号为 1,2,3,…,N。每堆石子有一定的质量，可以用一个整数来描述，现在要将这 N堆石子合并成为一堆。每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同。问题是：找出一种合理的方法，使总的代价最小，输出最小代价。
dp[i][j]:表示将 i 到 j 这一段石子合并成一堆的方案的集合，属性 Min
sum[i]:前缀和
枚举:区间长度+区间左端点
循环变量:len:1−N，i:1−n−(len−1)，j:i+len−1，k:i−j−1
dp[i][i]=0，len=1
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]−sum[i−1])，else
四 计数类dp
1.整数划分 （类完全背包 恰好装满背包）
一个正整数n可以表示成若干个正整数之和，形如：n=n1+n2+…+nk，其中 n1≥n2≥…≥nk,k≥1。我们将这样的一种表示称为正整数 n的一种划分。现在给定一个正整数 n，请你求出 n 共有多少种不同的划分方法。
dp[i][j]:数字i分解方案的最大数为j
预处理:f[0]=1
循环变量:i:1−N，j:i−n
dp[i][j]=min(dp[i−1][j−1],dp[i−j][j−1])
答案: res=0，i:1−n，res+=dp[n][i]
五 树形dp
1.没有上司的舞会
Ural 大学有 N 名职员，编号为 1∼N。他们的关系就像一棵以校长为根的树，父节点就是子节点的直接上司。每个职员有一个快乐指数，用整数 Hi给出，其中 1≤i≤N。现在要召开一场周年庆宴会，不过，没有职员愿意和直接上司一起参会。在满足这个条件的前提下，主办方希望邀请一部分职员参会，使得所有参会职员的快乐指数总和最大，求这个最大值。
dp[u][1]:以u为根的子树，选择u的最大快乐指数和
dp[u][0]:以u为根的子树，不选u的最大快乐指数和
dp[u][0]=∑max(dp[son][0],dp[son][1])
dp[u][1]=∑dp[son][0]
Code:
void dfs(int u) {
//st[u]=true; 不可以使用st数组
dp[u][1]=happy[u];
for(int i=h[u];~i;i=ne[i]) {
int j=e[i];
//if(!st[u]) {
dfs(j);
dp[u][0]+=max(dp[j][0],dp[j][1]);
dp[u][1]+=dp[j][0];
//}
}
}
六 记忆化搜索
1.滑雪
给定一个 R 行 C列的矩阵，表示一个矩形网格滑雪场。矩阵中第 i行第 j 列的点表示滑雪场的第 i 行第 j列区域的高度。一个人从滑雪场中的某个区域内出发，每次可以向上下左右任意一个方向滑动一个单位距离。当然，一个人能够滑动到某相邻区域的前提是该区域的高度低于自己目前所在区域的高度。现在给定你一个二维矩阵表示滑雪场各区域的高度，请你找出在该滑雪场中能够完成的最长滑雪轨迹，并输出其长度(可经过最大区域数)。
dp[x][y]:从x，y出发的最长滑雪轨迹
预处理:memset(dp,−1,sizeofdp)，dp[x][y]=1
dp[x][y]=max(dp[x][y],dfs(nx,ny)+1)
Code:
int dfs(int x,int y) {
if(dp[x][y]!=-1) return dp[x][y];
dp[x][y]=1;
for(int i=0;i<4;i++) {
int nx=x+dx[i],ny=y+dy[i];
if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&g[x][y]>g[nx][ny])
dp[x][y]=max(dp[x][y],dfs(nx,ny)+1);
}
return dp[x][y];
}
int main() {
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++) cin>>g[i][j];
memset(dp,-1,sizeof dp);
int res=0;
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
res=max(res,dfs(i,j));
}
}
cout<<res<<endl;
return 0;
}
七 数位dp
1.计数问题
给定两个整数 a 和 b，求 a 和 b 之间的所有数字中 0∼9 的出现次数。
dp[i][y][j][u]:满足i位，最高位为j的数中u出现的次数
预处理:dp[i][j][u]=pow(i−1)(ifj==u)
循环变量:i:1−N−1，j:0−9，k:0−9
dp[i][j][u]+=dp[i−1][k][u];
Code:
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <math.h>
using namespace std;
const int N = 18;
int n, m;
int dp[N][10][10];
void init() {
for(int i=1;i<N;i++) {
for(int j=0;j<10;j++) {
for(int u=0;u<10;u++) {
if(j==u) dp[i][j][u]=pow(10,i-1);
for(int k= 0;k<10;k++) {
dp[i][j][u]+=dp[i-1][k][u];
}
}
}
}
}
int solve(int n,int u) {
if(!n) return u==0;
vector<int> nums;
while(n) nums.push_back(n%10),n/=10;
int res=0,last=0;
for(int i=nums.size()-1;i>=0;i--) {
int x=nums[i];
for(int j= i==nums.size()-1;j<x;j++) {
res+=last*pow(10,i)+dp[i+1][j][u];
}
if(x==u) last++;
if(!i) res+=last;
}
for(int i=1;i<nums.size();i++){
for(int j= i!=1;j<10;j++){
res+=dp[i][j][u];
}
}
return res+(nums.size()==1&&u==0); //确保 u==0 时候返回的答案 是 0~n中0出现的次数
//u!=0 是 统计1-n中数字出现的次数
}
int main()
{
init();
int a,b;
while(~scanf("%d%d", &a, &b),a||b) {
if(a>b) swap(a,b);
for(int u=0;u<10;u++) {
printf("%d ", solve(b,u)-solve(a-1,u));
}
printf("\n");
}
return 0;
}
