动态规划（01背包、完全背包、多重部分和、LCS、LIS、划分数、多重集组合数）动态规划

【动态规划（01背包、完全背包、多重部分和、LCS、LIS、划分数、多重集组合数）】编辑器存在大小不一的情况，更好的阅读体验可戳WizNote：动态规划
01背包 dp[i][j]:从第i个物品开始挑选总重小于j时，总价值的最大值 O(nW) （i逆序，j顺序） i:n-1~0 j:0~W 1.没有剩余物品（i<0) 2.无法挑选这个物品(j dp[i][j]:前i个物品总重量不超过j 的物品时总价值的最大值（i顺序，j顺序） i:1~n j:0~W ★初始化dp[0][j] = 0（dp[i-1][j]状态时会用到并且 i=0时相当于没有选取物品） 1.没有剩余物品（i>n) 2.无法挑选这个物品(j 入门题：HDU 2602

#include #include #include #include using namespace std; const int N = 1e3 + 10; int dp[N][N]; int w[N], v[N]; int main() { int t; scanf("%d", &t); while(t--) { memset(dp, 0, sizeof(dp)); int n, V; scanf("%d %d", &n, &V); for(int i = 1; i <= n; i++) { scanf("%d", &v[i]); } for(int i = 1; i <= n; i++) { scanf("%d", &w[i]); } for(int i = 1; i <= n; i++) { for(int j = 0; j <= V; j++){ if(j < w[i]){ dp[i][j] = dp[i - 1][j]; } else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]); } } printf("%d\n", dp[n][V]); } }

最长公共子序列（LCS） s1~snt1~tn
dp[i][j] :s1...si和t1...tj对应的LCS长度
s1...si+1和t1..ti+1对应的公共子序列可能是 si+1=ti+1时，在s1..si和t1...tj的LCS末尾追加上si+1
s1..si和t1..tj+1的LCS
s1..si+1和t1..tj的LCS

dp[i+1][j+1]=dp[i][j]+1(si+1=tj+1) =max(dp[i][j+1],dp[i+1][j]) (其他）
入门题：POJ 1458

#include #include #include #include using namespace std; const int N = 1e3 + 10; char s[N], t[N]; int dp[N][N]; int main(){ while(~scanf("%s %s", s, t)){ memset(dp, sizeof(dp), 0); int n = strlen(s); int m = strlen(t); for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ if(s[i] == t[j]){ dp[i+1][j+1] = dp[i][j] + 1; } else{ dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j]); } } } printf("%d\n", dp[n][m]); } }

完全背包
dp[i][j]:前i个物品总重量不超过j 的物品时总价值的最大值 dp[0][j]=0
i:1~n j:0~W k:0~k*w[i] dp[i][j]=dp[i-1][j](j 本质是当前的状态选取k个时，直接从当前选取k-1个的状态转移过来

入门题：HDU 1248

#include #include #include #include using namespace std; const int N = 1e4 + 10; int dp[5][N]; int main(){ int w[4] = {0, 150, 200, 350}; int t,W; scanf("%d", &t); while(t--){ memset(dp, 0, sizeof(dp)); scanf("%d", &W); for(int i = 1; i <= 3; i++){ for(int j = 0; j <= W ; j++){ if(j < w[i]){ dp[i][j] = dp[i - 1][j]; } else dp[i][j] = max(dp[i - 1][j], dp[i][j - w[i]] + w[i]); } } printf("%d\n", W - dp[3][W]); } }

一维数组的实现（空间复杂度降低） 01背包： i:1~n j: W~w[i] dp[j]=max(dp[j],dp[j-w[i]]+v[i]) 完全背包： i:1~n j: w[i]~W dp[j]=max(dp[j],dp[j-w[i]]+v[i])
★ 只有循环的方向不同
多重部分和问题： ai mi K dp[i+1][j]:用前i种数加和得到j时第i种数最多能剩余多少个 O(nK) 1. 前面已经加到j dp[i+1][j]=m[i]dp[i][j]≥0 2. 不能加的情况：当前a[i]>j 或前i+1个数加到j-a[i]时已经没有剩余 dp[i+1][j-a[i]]≤0 3. 前面已经加到 j-a[i] 这里还需要一个a[i] dp[i+1][j]=dp[i+1][j-a[i]]-1 +数组重复利用：

int dp[MAX_K + 1];
void solve() {
memset(dp, -1, sizeof(dp));
dp[0] = 0;
for (int i = 0; i < n; i++){
for (int j = 0; j < W; j++){
if (dp[j] >= 0) dp[j] = m[i];
else if (j < a[i] || dp[j - a[i]] <= 0) dp[j] = -1;
else dp[j] = dp[j - a[i]] - 1;
}
}
if(dp[K] >= 0) puts("YES");
else puts("NO");
}

最长上升子序列（LIS） a[i] n dp[i]:长度为i的上升子序列中末尾元素的最小值（没有则不存在） O(nlogn) j:1~n i:1~n 用INF填充表示不存在 1. j==1 dp[i]=a[j] 2.直到找到 dp[i-1]找到a[j]>dp[i-1]的位置的后一位，把当前位置的dp[i]替换成min(dp[i],a[i])
因为第二步查找可以用二分所以可把原来为n 2的复杂度降为nlogn
*lower_bound(dp,dp+n,a[i]) ai -1i≤a i+1 *upper_bound: a i-1<=a ii+1
入门题：HDU 5748

#include #include #include #include using namespace std; const int N = 1e5 + 10; const int INF = 0x3f3f3f3f; int a[N], b[N]; int dp[N]; int main(){ int t; scanf("%d", &t); while (t--){ int n; scanf("%d", &n); memset(dp, INF, sizeof(dp)); for (int i = 1; i <= n; i++){ scanf("%d", &a[i]); } for (int i = 1; i <= n; i++){ *lower_bound(dp, dp + n, a[i]) = a[i]; b[i]=lower_bound(dp, dp + n, a[i]) - dp + 1; } for (int i = 1; i < n; i++){ printf("%d ", b[i]); } printf("%d\n", b[n]); } }

需要注意的是，该题是让求一个b[i]，使得LIS(b[i])=a[i]且b[i]要字典序最小，其实就是得到每个位置上的LIS。每个位置在用lower_bound求取时也已经可以得到注意lower_bound和upper_bound的用法即可。
计数问题dp：划分数：n个无区别物品划分成m组 dp[i][j]:j的i划分总数每一步有两种选择 1）用掉当前最大数减去之后继续 2）不用了最大数-1；

int f(int n,int idx){
if(n==0) return 1;
if(idx<=0) return 0;
return f(n-idx,idx)+f(n,idx-1);
}

i:1~n j:1~m dp[i][j]=dp[i-j][j]+dp[i][j-1] (O(nm))

多重集组合数：n种物品每种ai个（不同种类物品不同同种物品相同）从中取出m个 dp[i+1][j]：从前i种物品中取出j种的方案数每一个dp[i+1][j] 都是由从前i-1种物品取东西转移过来 dp[i][j-0]+dp[i][j-1]+...+dp[i][j-min(ai,j)] dp[i+1][j]= dp[i][j-0]+dp[i][j-1]+...+dp[i][j-min(ai,j)]=dp[i][j]+dp[i][j-1]+dp[i][j-1-1]+dp[i][j-1-2]+...+dp[i][j-1-(min(ai,j)-1)] =dp[i][j]+dp[i+1][j-1]-dp[i][j-1-min(ai,j)] i:0~n j:0~m 题目可戳： POJ 3046