一维dp知识点

1.一维DP的核心用一维数组dp[i]记录状态通过清晰的递推关系状态转移求解。2. 基础模型线性递推核心是找到dp[i]和dp[i-1]、dp[i-2]的关系。爬楼梯dp[i] dp[i-1] dp[i-2]最小花费爬楼梯dp[i] min(dp[i-1], dp[i-2]) cost[i]3. 经典线性DP这类问题通常需要在数组或序列上进行决策。最大子段和dp[i] max(nums[i], dp[i-1] nums[i])最长上升子序列 (LIS)这是重中之重其定义状态的方式以i结尾和转移思想向前查找是解决很多难题的关键 。4. 一维DP优化技巧滚动数组当dp[i]只依赖于前几个状态时可以用几个变量代替整个数组将空间复杂度从 O(n) 降到 O(1) 。二维转一维背包问题核心这是最难也是最关键的部分。以01背包为例核心优化是一维数组必须逆序遍历背包容量以确保每个物品只被选一次。这个思想会贯穿所有背包问题 。模型背包类型特点核心代码一维优化版01背包每种物品只能选0或1个for (int jm; jv[i]; j--) dp[j] max(dp[j], dp[j-v[i]] w[i]);完全背包每种物品可以选无限个for (int jv[i]; jm; j) dp[j] max(dp[j], dp[j-v[i]] w[i]);多重背包每种物品有数量限制使用二进制优化将问题分解为01背包01背包int dp[maxV] {0}; for (int i 1; i n; i) { // 遍历物品 int v, w; cin v w; // 体积价值 for (int j m; j v; j--) { // 容量逆序 dp[j] max(dp[j], dp[j - v] w); } } cout dp[m] endl;完全背包int dp[maxV] {0}; for (int i 1; i n; i) { int v, w; cin v w; for (int j v; j m; j) { // 容量正序 dp[j] max(dp[j], dp[j - v] w); } } cout dp[m] endl;多重背包int dp[maxV] {0}; for (int i 1; i n; i) { int v, w, s; cin v w s; // 体积价值数量 // 二进制拆分 for (int k 1; k s; k 1) { int val k * v, wei k * w; for (int j m; j val; j--) { // 01背包逆序 dp[j] max(dp[j], dp[j - val] wei); } s - k; } if (s 0) { // 剩余部分 int val s * v, wei s * w; for (int j m; j val; j--) { dp[j] max(dp[j], dp[j - val] wei); } } } cout dp[m] endl;例题装箱问题题目描述有一个箱子容量为 V正整数0≤V≤20000同时有0≤V≤20000同时有n个物品个物品0 \leq n \leq 30$每个物品有一个体积正整数。要求 nn 个物品中任取若干个装入箱内使箱子的剩余空间为最小。输入描述输入第一行一个整数表示箱子容量。第二行一个整数 nn表示有 nn 个物品。接下来 nn 行分别表示这 nn 个物品的各自体积。输出描述输出一行表示箱子剩余空间。输入输出样例示例 1输入24 6 8 3 12 7 9 7输出0#includebits/stdc.h using namespace std; int dp[30000]; int main() {ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int t,m; cintm; for(int i1;im;i) { int shj; cinshj; for(int jt;jshj;j--) { dp[j]max(dp[j],dp[j-shj]shj);//dp要表示体积将价值改为shj即可 } } coutt-dp[t]; return 0; }你有一架天平和 NN 个砝码这 NN 个砝码重量依次是 W1,W2,⋅⋅⋅,WNW1​,W2​,⋅⋅⋅,WN​。请你计算一共可以称出多少种不同的重量 注意砝码可以放在天平两边。输入格式输入的第一行包含一个整数 NN。第二行包含 NN 个整数W1,W2,W3,⋅⋅⋅,WNW1​,W2​,W3​,⋅⋅⋅,WN​。输出格式输出一个整数代表答案。样例输入3 1 4 6样例输出10样例说明能称出的 1010 种重量是1、2、3、4、5、6、7、9、10、111、2、3、4、5、6、7、9、10、11​。111126−4(26−4(天平一边放 66另一边放 4)4)​34−134−1444456−156−1​6666716716946−1946−11046104611146。11146。#include bits/stdc.h using namespace std; typedef long long ll; ll N; ll a[200]; ll summ0; ll ans0; int dp[200][200000]; //dp[i][j]表示用到前i个砝码能否称出j重量 //1为可以0为不可以 int main() { // 请在此输入您的代码 cinN; for(int i1;iN;i){ cina[i]; summa[i]; } for(int i1;iN;i){ for(int j1;jsumm;j){//遍历所有可能的重量 dp[i][j]dp[i-1][j];//继承前一个状态 if(dp[i][j]0){//如果普通继承下来发现这个不行呢 if(ja[i]) dp[i][j]1;//如果需要的重量正好就是第i个砝码那么可以 if(dp[i-1][ja[i]]1) dp[i][j]1;//如果前i-1个能搞出ja[i]重量那么把第i个砝码放到另一侧就行 if(dp[i-1][abs(j-a[i])]1) dp[i][j]1;//如果前i-1个砝码能搞出abs(j-a[i])重量 //那么把第i个砝码放同侧就行 } } } for(int j1;jsumm;j){ if(dp[N][j]1) ans;//遍历看dp[][]1的个数就是答案 } coutansendl; return 0; }小明几乎每天早晨都会在一家包子铺吃早餐。他发现这家包子铺有种蒸笼其中第种蒸笼恰好能放个包子。每种蒸笼都有非常多笼可以认为是无限笼。每当有顾客想买个包子卖包子的大叔就会迅速选出若干笼包子来使得这若干笼中恰好一共有个包子。比如一共有 3 种蒸笼分别能放 3、4 和 5 个包子。当顾客想买 11 个包子时大叔就会选 2 笼 3 个的再加 1 笼 5 个的也可能选出 1 笼 3 个的再加 2 笼 4 个的。当然有时包子大叔无论如何也凑不出顾客想买的数量。比如一共有 3 种蒸笼分别能放 4、5 和 6 个包子。而顾客想买 7 个包子时大叔就凑不出来了。小明想知道一共有多少种数目是包子大叔凑不出来的。输入描述第一行包含一个整数(1≤≤100)。以下 N 行每行包含一个整数(1≤≤100)。输出描述一个整数代表答案。如果凑不出的数目有无限多个输出 INF。输入输出样例示例 1输入245输出6样例说明凑不出的数目包括1, 2, 3, 6, 7, 11。示例 2输入246输出INF样例说明所有奇数都凑不出来所以有无限多个#include iostream #include cstdio using namespace std; const int N 1e7; int num[105]; int dp[N]; int main() { // 请在此输入您的代码 int n; int des 0; scanf(%d,n); for(int i1;in;i) { scanf(%d,num[i]); dp[num[i]]; } for(int i1;iN;i) { for(int j1;jn;j) { if(i-num[j]0) { continue; } dp[i]dp[i-num[j]]dp[i]; if(dp[i]!0) { break; } } if(dp[i]0) { des; } } if(des10000) { printf(INF); return 0; } printf(%d,des); return 0; }题目描述小明开了一家糖果店。他别出心裁把水果糖包成 4 颗一包和 7 颗一包的两种。糖果不能拆包卖。小朋友来买糖的时候他就用这两种包装来组合。当然有些糖果数目是无法组合出来的比如要买 10 颗糖。你可以用计算机测试一下在这种包装情况下最大不能买到的数量是 17。大于 17 的任何数字都可以用 4 和 7 组合出来。本题的要求就是在已知两个包装的数量时求最大不能组合出的数字。输入描述输入两个正整数表示每种包装中糖的颗数(都不多于 1000 )。输出描述输出一个正整数表示最大不能买到的糖数。不需要考虑无解的情况输入输出样例示例输入4 7输出17#includeiostream #includequeue using namespace std; int dp[10000005]; int arr[3]; int maxx 0; int main() { cin arr[1] arr[2]; dp[arr[1]] 1; dp[arr[2]] 1; for (int i 1;i 3;i) { for (int j arr[i];j 10000000;j) { if (dp[j]) { dp[j arr[i]] 1; } if (dp[j]0) maxx j; } } cout maxx endl; return 0; }题目描述小明有一个容量为 VV 的背包。这天他去商场购物商场一共有 NN 种物品第 ii 种物品的体积为 wiwi​价值为 vivi​数量为 sisi​。小明想知道在购买的物品总体积不超过 VV 的情况下所能获得的最大价值为多少请你帮他算算。输入描述输入第 11 行包含两个正整数 N,VN,V表示商场物品的数量和小明的背包容量。第 2∼N12∼N1 行包含 33 个正整数 w,v,sw,v,s表示物品的体积和价值。1≤N≤1021≤N≤1021≤V≤2×1021≤V≤2×1021≤wi,vi,si≤2×1021≤wi​,vi​,si​≤2×102。输出描述输出一行整数表示小明所能获得的最大价值。输入输出样例示例 1输入3 30 1 2 3 4 5 6 7 8 9输出39#includeiostream #includealgorithm using namespace std; const int N 1010; int n, m; int v[2*N], w[2*N], s[2*N]; int f[2*N][2*N]; int main(){ cin n m; for(int i 1; i n; i) { cin v[i] w[i] s[i]; } for(int i 1; i n; i){ for(int j 0; j m; j) { for(int k 0; k s[i] k * v[i] j; k) { f[i][j] max(f[i][j], f[i - 1][j - k * v[i]] k *w[i]); } } } cout f[n][m]; return 0; }