动态规划（入门/背包/状态机/划分/区间/状压/数位/树形/数据结构优化）By 灵茶山艾府
AI-摘要
切换
Tianli GPT
AI初始化中...
介绍自己
生成本文简介
推荐相关文章
前往主页
前往tianli博客
一、入门 DP
§1.1 爬楼梯 //有顺序的排列
爬1,2阶的方案数：dp[i]=dp[i-1]+dp[i-2]
int climbStairs(int n) {
if(n<=1)return n;
vector<int> dp(n+1);
dp[1]=1;dp[2]=2;
for(int i=3;i<=n;i++)
dp[i]=dp[i-1]+dp[i-2];
return dp[n];
}
爬1,2阶的最小花费：dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
int minCostClimbingStairs(vector<int>& cost) {
int n=cost.size();
vector<int> dp(n+1);
dp[0]=dp[1]=0;
for(int i=2;i<=n;i++)
dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
return dp[n];
}
相当于你可以走nums[j]步 dp[i]=\sum_{j=0}^{j<n} dp[i-nums[j]]
int combinationSum4(vector<int>& nums, int target) {
vector<int> dp(target+1,0);
dp[0]=1;
for(int i=1;i<=target;i++){
for(auto t:nums){
if(i>=t)
dp[i]=(1LL*dp[i]+dp[i-t])%INT_MAX;
}
}
return dp[target];
}
- 2466. 统计构造好字符串的方案数 1694
爬zero,one阶的最小花费
const int MOD=1e9+7;
int countGoodStrings(int low, int high, int zero, int one) {
vector<int> dp(high+1,0);
dp[0]=1;
for(int i=1;i<=high;i++){
if(i>=zero) dp[i]=(dp[i]+dp[i-zero])%MOD;
if(i>=one) dp[i]=(dp[i]+dp[i-one])%MOD;
}
int res=0;
for(int i=low;i<=high;i++) res=(res+dp[i])%MOD;
return res;
}
- 2266. 统计打字方案数 1857
对于字符串中字母完全相同的连续最大字串，例如22222
可求出每次可以跳1-3阶走完这个字串的方案数
对于两种情况（3个字母按键，4个字母按键）分别打表
对于每个符合条件的字串满足乘法法则，结果即为每个字串的方案数累乘
int countTexts(string s) {
//将问题转化为多个相同字母字串
//每个字串可以构成多少方案
//类似于可取跳1-3阶台阶
const int MOD=1e9+7,N=1e5+1;
int n=s.length(),t1[N]={0},t2[N]={0};
t1[0]=t2[0]=1;t1[1]=t2[1]=1;t1[2]=t2[2]=2;t1[3]=t2[3]=4;
for (int i=4;i<N;i++){
t1[i]=(1LL*t1[i-1]+t1[i-2]+t1[i-3])%MOD;
t2[i]=(1LL*t2[i-1]+t2[i-2]+t2[i-3]+t2[i-4])%MOD;
}
int ans=1;
for(int i=0;i<n;){
int cnt=0,num=s[i];
for(;num==s[i]&&i<n;i++) cnt+=1;
ans=1LL*ans*(num!='7'&&num!='9'?t1[cnt]:t2[cnt])%MOD;
}
return ans;
}
§1.2 打家劫舍
设dp[i]为合理取舍0~i的最大金额
dp[i]=max(dp[i-2]+nums[i],dp[i-1])
int rob(vector<int>& nums) {
int n=nums.size();
if (n==0) return 0;
if (n==1) return nums[0];
vector<int> dp(n,0);
dp[0]=nums[0];
dp[1]=max(nums[0],nums[1]);
for(int i=2;i<n;i++)
dp[i]=max(dp[i-2]+nums[i],dp[i-1]);
return dp[n-1];
}
题目元素最大值为1e4，创建数组cnt将每个值映射到cnt的下标中，记录出现次数
转化为在这10000个房子中打家劫舍，偷第i间房子的价值为i*cnt[i]
int deleteAndEarn(vector<int>& nums) {
int cnt[10001]={0};
for(auto t:nums) cnt[t]++;
vector<int> dp(10001,0);
dp[0]=0,dp[1]=cnt[1];
for(int i=2;i<=10000;i++)
dp[i] = max(dp[i-2]+i*cnt[i],dp[i-1]);
return dp[10000];
}
- 2320. 统计放置房子的方式数 1608
对一行打家劫舍求结果dp[n]，方案数为dp[n]^2
const int MOD=1e9+7;
int countHousePlacements(int n) {
vector<int> dp(n+1,0);
dp[0]=1;
dp[1]=2;
for(int i=2;i<=n;i++)
dp[i]=(dp[i-1]+dp[i-2])%MOD;
return (1LL*dp[n]*dp[n])%MOD;
}
环形打家劫舍
避免第一家和最后一家同时被偷窃，我们可以指定区间偷窃
偷第一家fun(0,n-2)，偷最后一家fun(1,n-1)
int rob(vector<int>& nums) {
int n=nums.size();
if (n==0) return 0;
if (n==1) return nums[0];
auto fun=[&](int l,int r){
if (l==r) return nums[l];
vector<int> dp(n,0);
dp[l]=nums[l];
dp[l+1]=max(nums[l],nums[l+1]);
for(int i=l+2;i<=r;i++)
dp[i]=max(dp[i-2]+nums[i],dp[i-1]);
return dp[r];
};
return max(fun(0,n-2),fun(1,n-1));
}
挑战关：
- 1388. 3n 块披萨 2410
- 2597. 美丽子集的数目 *用 DP 解决
- 2638. 统计 K-Free 子集的总数（会员题）上面这题的加强版
§1.3 最大子数组和（最大子段和）
f[i] = max(f[i-1] , 0) + a[i]
int maxSubArray(vector<int>& nums) {
int n=nums.size();
vector<int> f(n);
f[0]=nums[0];
for(int i=1;i<n;i++){
f[i]=max(f[i-1],0)+nums[i];
}
return *max_element(f.begin(),f.end());
}
- 2606. 找到最大开销的子字符串 1422
价值转换：使用idx数组，idx[a]表示字符a出现chars的下标
若idx[j]=-1说明没找到，价值为j+1
反之为vals[idx[j]]
int maximumCostSubstring(string s, string chars, vector<int>& vals) {
vector<int> idx(27,-1);
for(int i=0;i<chars.size();i++)
idx[chars[i]-'a']=i;
int n=s.length();
vector<int> f(n+1);
for(int i=1;i<=n;i++){
int j=s[i-1]-'a';
f[i]=max(f[i-1],0)+(idx[j]==-1?j+1:vals[idx[j]]);
}
return *max_element(f.begin(),f.end());
}
- 1749. 任意子数组和的绝对值的最大值 1542
将问题转化为求最大子数组和和最小子数组和，两者最大的即为答案
int maxAbsoluteSum(vector<int>& nums) {
int n=nums.size();
vector<int> f(n),g(n);
f[0]=g[0]=nums[0];
for(int i=1;i<n;i++){
f[i]=max(f[i-1],0)+nums[i];
g[i]=min(g[i-1],0)+nums[i];
}
return max(
*max_element(f.begin(),f.end()),
*min_element(g.begin(),g.end())*-1
);
}
- ⭐1191. K 次串联后最大子数组之和 1748
分类讨论：
k=1时，此时相当于求最大子数组和
k=2时，此时的特殊情况为最大子数组所包含的左右区间分别在两个数组中
k>2时，讨论子数组总和是否大于0，若大于0，说明每整个数组都可以子数组的一部分
此时答案为k=2时的解在中间加上k-2个sum
const int MOD=1e9+7;
int kConcatenationMaxSum(vector<int>& arr, int k) {
int n=arr.size();
vector<long long> f(n*min(k,2)+1);
for(int i=1;i<=n*min(k,2);i++)
f[i]=max(f[i-1],0LL)+1LL*arr[(i-1)%n];
int ans=*max_element(f.begin(),f.end())%MOD,
sum=accumulate(arr.begin(),arr.end(),0);
while(sum>0&&--k>=2) ans=(ans+sum)%MOD;
return ans;
}
- 918. 环形子数组的最大和 1777
答案要么区间要么在数组内部，要么在数组两边
在数组内部：通常解法，子数组最大值
在数组两边：用数组和减去中间部分，使其中间部分最小即可
特殊情况：最小和即为整个数组和，但是可能存在一些子数组的和会大于0，此时答案取子数组最大值
int maxSubarraySumCircular(vector<int>& nums) {
int max_res=INT_MIN,min_res=0;
int max_f=0,min_f=0,sum=0;
for(auto t:nums){
max_res=max(max_res,max_f=max(max_f,0)+t);
min_res=min(min_res,min_f=min(min_f,0)+t);
sum+=t;
}
return min_res==sum?max_res:max(max_res,sum-min_res);
}
- 2321. 拼接数组的最大分数 1791
将b数组的第i个值替换到a数组，相当于i位置的值增加了b[i]-a[i]，若想得到a数组的总和最大值，相当于求b[i]-a[i]的最大子数组和res
对于a数组的最大值即为sum(a)+res，考虑b两者交换一下即可，两者最大值即为答案
int fun(vector<int>& a, vector<int>& b){
int n=a.size();
int res=0,f=0,sum=0;
for(int i=0;i<n;i++){
sum+=a[i];
res=max(res,f=max(f,0)+b[i]-a[i]);
}
return sum+res;
}
int maximumsSplicedArray(vector<int>& a, vector<int>& b) {
return max(fun(a,b),fun(b,a));
}
1.暴力+二维前缀和
①for i j 枚举右下角点位
②for p q 枚举左上角点位
③求s(ijpq)所有小于k的最大值
2.二分优化
枚举 top上边界 bot下边界 r左边界，二分l边界，使用logn复杂度找到
s(top bot r l)小于k时，l所在的位置
int maxSumSubmatrix(vector<vector<int>>& mat, int k) {
int m = mat.size(), n = mat[0].size();
vector<vector<int>> s(m+1,vector<int>(n+1));
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
s[i][j]=mat[i-1][j-1]+
s[i-1][j]+s[i][j-1]-s[i-1][j-1];
int ans=INT_MIN;
// METHOD1 => 朴素前缀和
// for(int i=1;i<=m;i++)
// for(int j=1;j<=n;j++)
// for(int p=i;p<=m;p++)
// for(int q=j;q<=n;q++){
// int cur = s[p][q]-s[i-1][q]-s[p][j-1]+s[i-1][j-1];
// if(cur<=k) ans = max(ans,cur);
// }
// METHOD2 => 二分优化
for(int top=1;top<=m;top++){
for(int bot=top;bot<=m;bot++){
set<int> st;
st.insert(0);
for(int r=1;r<=n;r++){
int right = s[bot][r]-s[top-1][r];
auto left = st.lower_bound(right-k);
if(left != st.end()){
int cur = right-*left;
ans=max(ans,cur);
}
st.insert(right);
}
}
}
// METHOD3 => 最大化二分
// for(int i=1;i<=(n>m?m:n);i++){
// for(int j=i;j<=(n>m?m:n);j++){
// set<int> st;st.insert(0);
// for(int fixed = 1; fixed <= (n > m ? n : m); fixed++){
// int a = n>m ?
// s[j][fixed] - s[i-1][fixed] :
// s[fixed][j] - s[fixed][i-1] ;`
// auto b=st.lower_bound(a - k);
// if(b!=st.end()){
// int cur = a - *b;
// ans = max(ans,cur);
// }
// st.insert(a);
// }
// }
// }
return ans;
}
思维扩展：
挑战关：
- 2272. 最大波动的子字符串 2516
二、网格图 DP
§2.1 基础
左上到右下的最大价值dp
int jewelleryValue(vector<vector<int>>& q) {
int n=q.size(),m=q[0].size();
vector<vector<int>> f(n+1,vector<int>(m+1));
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
f[i][j]=max(f[i-1][j],f[i][j-1])+q[i-1][j-1];
return f[n][m];
}
左上到右下的方案数dp
int uniquePaths(int m, int n) {
vector<vector<int>> dp(m,vector<int>(n,0));
for(int i=0;i<m;i++) dp[i][0]=1;
for(int j=0;j<n;j++) dp[0][j]=1;
for(int i=1;i<m;i++)
for(int j=1;j<n;j++)
dp[i][j]=dp[i-1][j]+dp[i][j-1];
return dp[m-1][n-1];
}
左上到右下带障碍的方案数dp
int uniquePathsWithObstacles(vector<vector<int>>& q) {
int m=q.size();
int n=q[0].size();
vector<vector<int>> dp(m,vector<int>(n,0));
for(int i=0;i<m&&q[i][0]==0;i++)dp[i][0]=1;
for(int j=0;j<n&&q[0][j]==0;j++)dp[0][j]=1;
for(int i=1;i<m;i++){
for(int j=1;j<n;j++){
if(q[i][j]==1) continue;
dp[i][j]=dp[i][j-1]+dp[i-1][j];
}
}
return dp[m-1][n-1];
}
左上到右下的最小价值dp
int minPathSum(vector<vector<int>>& q) {
int n=q.size(),m=q[0].size();
vector<vector<int>> f(n,vector<int>(m));
for(int t=0,sum=0;t<n;t++) sum+=q[t][0],f[t][0]=sum;
for(int t=0,sum=0;t<m;t++) sum+=q[0][t],f[0][t]=sum;
for(int i=1;i<n;i++)
for(int j=1;j<m;j++)
f[i][j]=min(f[i-1][j],f[i][j-1])+q[i][j];
return f[n-1][m-1];
}
int minimumTotal(vector<vector<int>>& q) {
int n=q.size();
//二维DP
// vector<vector<int>> f(n,vector<int>(n));
// f[0][0]=q[0][0];
// for(int i=1;i<n;i++){
// f[i][0]=f[i-1][0]+q[i][0];
// for(int j=1;j<q[i].size()-1;j++)
// f[i][j]=min(f[i-1][j],f[i-1][j-1])+q[i][j];
// f[i][i]=f[i-1][i-1]+q[i][i];
// }
// return *min_element(f[n-1].begin(),f[n-1].end());
//压缩一维dp
vector<int> f(n);
f[0]=q[0][0];
for(int i=1;i<n;i++){
f[i]=f[i-1]+q[i][i];
for(int j=q[i].size()-1-1;j>0;j--)
f[j]=min(f[j],f[j-1])+q[i][j];
f[0]=f[0]+q[i][0];
}
return *min_element(f.begin(),f.end());
}
- 931. 下降路径最小和 1573
int minFallingPathSum(vector<vector<int>>& q) {
int n=q.size();
vector<vector<int>> f(n,vector<int>(n));
f[0]=q[0];
for(int i=1;i<n;i++){
f[i][0]=min(f[i-1][0],f[i-1][1])+q[i][0];
for(int j=1;j<n-1;j++){
f[i][j]=min({f[i-1][j],f[i-1][j-1],f[i-1][j+1]})+q[i][j];
}
f[i][n-1]=min(f[i-1][n-1],f[i-1][n-2])+q[i][n-1];
}
return *min_element(f[n-1].begin(),f[n-1].end());
}
- 2684. 矩阵中移动的最大次数 1626
走完后将元素设为0防止重复走到该位置
int maxMoves(vector<vector<int>>& grid) {
int m=grid.size(),n=grid[0].size(),res=0;
function<void(int,int)> dfs=[&](int i,int j){
res=max(res,j);
if(res==n-1) return;
for(int k=max(i-1,0);k<min(i+2,m);k++)
if(grid[k][j+1]>grid[i][j])
dfs(k,j+1);
grid[i][j]=0;
};
for(int i=0;i<m;i++) {
dfs(i,0);
}
return res;
}
- 2304. 网格中的最小路径代价 1658
int minPathCost(vector<vector<int>>& grid, vector<vector<int>>& moveCost) {
int m=grid.size(),n=grid[0].size();
// 递归写法
// function<int(int,int)> dfs=[&](int i,int j)->int{
// if(i==m-1) return grid[i][j];
// int res=INT_MAX;
// for(int k=0;k<n;k++){
// res=min(res,dfs(i+1,k)+moveCost[grid[i][j]][k]);
// }
// return res+grid[i][j];
// };
vector<vector<int>> f(m,vector<int>(n,INT_MAX));
f[0]=grid[0];
for(int i=1;i<m;i++){
for(int j=0;j<n;j++){
for(int k=0;k<n;k++){
f[i][j]=min(f[i][j],f[i-1][k]+moveCost[grid[i-1][k]][j]+grid[i][j]);
}
}
}
return *min_element(f[m-1].begin(),f[m-1].end());
}
- 1289. 下降路径最小和 II 1697
int minFallingPathSum(vector<vector<int>>& q) {
int n=q.size();
//递归写法
// vector<vector<int>> memo(n,vector<int>(n,INT_MAX));
// function<int(int,int)> dfs=[&](int i,int j)->int{
// if(memo[i][j]!=INT_MAX) return memo[i][j];
// if(i==n-1) return q[i][j];
// int res=INT_MAX;
// for(int k=0;k<n;k++){
// if(j==k) continue;
// res=min(res,dfs(i+1,k));
// }
// return memo[i][j]=q[i][j]+res;
// };
// int res=INT_MAX;
// for(int j=0;j<n;j++){
// res=min(res,dfs(0,j));
// }
// return res;
//数组dp
vector<vector<int>> f(n,vector<int>(n,INT_MAX));
f[0]=q[0];
for(int i=1;i<n;i++){
for(int j=0;j<n;j++){
for(int k=0;k<n;k++){
if(j==k) continue;
f[i][j]=min(f[i-1][k]+q[i][j],f[i][j]);
}
}
}
return *min_element(f[n-1].begin(),f[n-1].end());
//tips：可以计算上一行的最大值和次大值优化k，化为o(n2+n);
}
§2.2 进阶
- 1594. 矩阵的最大非负积 1807
- 1301. 最大得分的路径数目 1853
- 2435. 矩阵中和能被 K 整除的路径 1952
- 174. 地下城游戏
- 741. 摘樱桃
- 1463. 摘樱桃 II 1957
- 329. 矩阵中的最长递增路径
- 2328. 网格图中递增路径的数目 2001
- 2267. 检查是否有合法括号字符串路径 2085
- 1937. 扣分后的最大得分 2106
- 2510. 检查是否有路径经过相同数量的 0 和 1（会员题）
三、背包
§3.1 0-1 背包
问题描述：有 N 件物品和一个容量为 V 的背包，每件物品有各自的价值且只能被选择一次，要求在有限的背包容量下，装入的物品总价值最大。
二维01背包：设f[i][j]前 i 个物品，背包容量 j 下的最优解
f[i][j]=max\left\{
\begin{array}{ll}
f[i-1][j] & \ j<v[i] \\
f[i-1][j-v[i]]+w[i] & \ 选择第i件物品 \\
f[i-1][j] & \ 不选择第i件物品 \\
\end{array} \right.
#include<bits/stdc++.h>
using namespace std;
const int N = 1005;
int v[N],w[N],f[N][N];
int main() {
int n,m; cin>>n>>m;
for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++){
if(j<v[i]) {
f[i][j]=f[i-1][j];
}
else {
f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]);
}
}
}
cout<<f[n][m]<<endl;
return 0;
}
一维优化：可以发现可以得到f[i][j]的状态都会依赖f[i-1]相关的状态，状态f[j]定义：N件物品，背包容量j下的最优解。
f[j] = max(f[j], f[j - v[i]] + w[i])
可以发先，f[j]会依赖于于上一次i-1的左侧结果推理出来，由于右侧推导的元素依赖于左方上一次i-1所推导出来的结果，若从左向右遍历，会导致推导出i的结果覆盖i-1的结果，导致右侧元素无法推导出来（i-1所推导的信息被新推导出的i信息覆盖），所以需要从右向左遍历
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int v[N],w[N],f[N];
int main() {
int n,V;cin>>n>>V;
for(int i=0;i<n;i++) cin>>v[i]>>w[i];
for(int i=0;i<n;i++)
for(int j=V;j>=v[i];j--)
f[j]=max(f[j],f[j-v[i]]+w[i]);
cout<<f[V];
}
- 2915. 和为目标值的最长子序列的长度 1659
//恰好装满型01背包
int lengthOfLongestSubsequence(vector<int>& A, int sum) {
vector<int> f(sum+1,INT_MIN);f[0]=0;
for(auto x:A)
for(int i=sum;i>=x;i--)
if(f[i-x]!=INT_MIN)
f[i]=max(f[i-x]+1,f[i]);
return f[sum]==INT_MIN?-1:f[sum];
}
int minRemainingSpace(vector<int>& N, int V) {
vector<int> f(V+1,0);
for(auto x:N){
for(int i=V;i>=x;i--){
f[i]=max(f[i],f[i-x]+x);
}
}
return V-f[V];
}
设数组和为sum，若sum为奇数，则无解，若为偶数计算0-1 sum/2的背包，最大价值为f[tar]
bool canPartition(vector<int>& nums) {
int sum=accumulate(nums.begin(),nums.end(),0);
if(sum%2) return false;
int tar=sum/2;
// 01背包
// vector<int> f(tar+1,0);
// for(auto x:nums){
// for(int i=tar;i>=x;i--){
// f[i]=max(f[i],f[i-x]+x);
// }
// }
// return f[tar]==sum-f[tar];
//恰好装满
vector<bool> f(tar+1,0);
f[0]=true;
for(auto x:nums){
for(int i=tar;i>=x;i--){
if(f[i-x])
f[i]=true;
}
}
return f[tar];
}
设将一些元素变为相反数之前的和为x，则存在x满足sum-2x=target
int findTargetSumWays(vector<int>& nums, int target) {
//sum - 2x = target
//x = (sum - targer) /2
int sum=accumulate(nums.begin(),nums.end(),0);
if((sum-target)%2||sum-target<0) return 0;
int tar=(sum - target) /2;
vector<int> f(tar+1,0);
f[0]=1;
for(auto x:nums){
for(int i=tar;i>=x;i--){
f[i]+=f[i-x];
}
}
return f[tar];
}
int numberOfWays(int n, int x) {
const int MOD=1e9+7;
vector<int> f(n+1,0);
f[0]=1;
for(int i=1;;i++){
int val=pow(i,x);
if(val>n) break;
for(int j=n;j>=val;j--){
f[j]=(f[j]+f[j-val])%MOD;
}
}
return f[n];
}
- 474. 一和零（二维背包）
int findMaxForm(vector<string>& strs, int m, int n) {
vector<vector<int>> dp(m+1,vector<int>(n+1,0));
for(auto s:strs){
int x=0,y=0;
for(auto &c:s)
c=='0'?x++:y++;
for(int i=m;i>=x;i--)
for(int j=n;j>=y;j--)
dp[i][j]=max(dp[i][j],dp[i-x][j-y]+1);
}
return dp[m][n];
}
- 1049. 最后一块石头的重量 II 2092
将石头分成两堆，求一堆石头的01 sum/2，此时一堆石头的重量为f[tar]，另一堆为sum-f[tar]
int lastStoneWeightII(vector<int>& stones) {
int sum=accumulate(stones.begin(),stones.end(),0);
int tar=sum/2;
vector<int>f(tar+1,0);
for(auto x:stones)
for(int j=tar;j>=x;j--)
f[j]=max(f[j],f[j-x]+x);
return (sum-f[tar])-f[tar];
}
暴力+01背包
根据题目范围，target最大为1e4，方案若超过这个值要取最小，假设都超过这个值，那么最小为一份主料+一份辅料为2e4
可以说明我们只需要求01 20000的背包即可
f[i]表示是否可以得到成本为i的方案
遍历后只需要找到最靠近target的i即可
int closestCost(vector<int>& baseCosts, vector<int>& toppingCosts, int target) {
const int N=20000;
vector<bool> f(N+1);
for(auto x:baseCosts) f[x]=1;
for(auto x:toppingCosts){
for(int w=0;w<2;w++){
for(int i=N;i>=x;i--){
f[i]=f[i-x]||f[i];
}
}
}
int res=0;
for(int i=0,tmp=INT_MAX;i<=N;i++){
if(f[i]&&abs(i-target)<tmp){
res=i;
tmp=abs(i-target);
}
}
return res;
}
- ⭐879. 盈利计划 2204
1.数据理解
profit[i]：利润
group[i]：人数成本
n:总人数，minProfit:至少利润
2.状态定义
考虑前i个工作，使用人数为j，至少利润为k的方案数
3.初始化
根据定义 f[0][j][0] = 1
4.状态推导
①若不选择当前第i个工作，此时方案数为f[i-1][j][k]
②若选择当前第i个工作
第i个工作的下标为i-1
j可以由 j-group[i-1] 状态转化过来
k可以由k-profit[i-1]转化过来，考虑表达式可能存在负值，根据定义，负值也满足要求，我们可以把负值到0的状态都用f[i][j][0]来存储
此时方案数为f[i-1][j-group[i-1]][max(k-profit[i-1],0)]
综上所述 f[i][j][k]即为不选和选的方案数之和，f[arrsize][n][minProfit]即为所求答案
f[i][j][k]=sum\left\{
\begin{array}{ll}
f[i-1][j][k] & \ 不选 \\
f[i-1][j-group[i-1]][max(k-profit[i-1],0)] & \ 选j>=group[i-1] \\
\end{array} \right.
int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {
const int N=101,MOD=1e9+7;
int f[N][N][N]={0};
for(int j=0;j<=n;j++)
f[0][j][0]=1;
int m=profit.size();
for(int i=1;i<=m;i++){
for(int j=0;j<=n;j++){
for(int k=0;k<=minProfit;k++){
f[i][j][k]=f[i-1][j][k];
if(j>=group[i-1]){
f[i][j][k]=(f[i-1][j][k]*1LL+f[i-1][j-group[i-1]][max(k-profit[i-1],0)])%MOD;
}
}
}
}
return f[m][n][minProfit];
}
- 3082. 求出所有子序列的能量和 ~2300
- 956. 最高的广告牌 2381
- 2518. 好分区的数目 2415
- 2742. 给墙壁刷油漆 2425
- LCP 47. 入场安检
- 2291. 最大股票收益（会员题）
- 2431. 最大限度地提高购买水果的口味（会员题）
§3.2 完全背包
问题描述：有 N 件物品和一个容量为 V 的背包，每件物品有各自的价值能被选择多次，要求在有限的背包容量下，装入的物品总价值最大。
二维01背包：设f[i][j]前 i 个物品，背包容量 j 下的**最优解**，设k为枚举取k次改件物品
f[i][j]=\mathop{\max}\limits_{k=0}^{k*v[i]<=j}(f[i-1][j-k*v[i]]+k*w[i]) \ 选择k个第i件物品 \\
#include<iostream>
using namespace std;
const int N = 1e3+10;
int v[N],w[N],f[N][N];
int main(){
int n,m;cin>>n>>m;
for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
for(int i=1;i<=n;i++){
for(int j=0;j<=m;j++){
for(int k=0;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]<<endl;
}
有没有什么办法优化k呢
我们可以发现f[i][j]展开如下
f[i][j]=max(f[i-1][j],f[i-1][j-v]+w,f[i-1][j-2*v]+2*w,f[i-1][j-3*v]+3*w,.....)
是否可以找到某种状态时f[i,j]max序列中的子序列呢
f[i,j-v]= max(f[i-1][j-v],f[i-1][j-2*v]+w,f[i-1][j-3*v]+2*w,.....)
对于这两种状态，满足条件的k的最大值对于相同的第i个物品时不变的，可以转化递推公式
f[i][j]=
\mathop{max}
%\limits_{下界}^{上界}
\begin{cases}
&f[i-1][j] &\text{不选和选不了的情况j<v[i]} \\
&max(f[i][j-v]+w,f[i-1][j]) &\text{j>=v[i]} \\
\end{cases}
#include<iostream>
using namespace std;
const int N = 1e3+10;
int v[N],w[N],f[N][N];
int main(){
int n,m;cin>>n>>m;
for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
for(int i=1;i<=n;i++){
for(int j=0;j<=m;j++){
f[i][j]=f[i-1][j];
if(j-v[i]>=0)
f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);
}
}
cout<<f[n][m]<<endl;
}
一维优化
可以发现f[i][j]依赖由上一层i-1推导的数据和左方推导出的这一层i的数据
所以可以设状态f[j]：N件物品，背包容量j下的最优解
f[j] = max(f[j],f[j-v[i]]+w[i]);
注意从左向右递推
#include<iostream>
using namespace std;
const int N = 1e3+10;
int v[N],w[N],f[N];
int main(){
int n,m; cin>>n>>m;
for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
for(int i=1;i<=n;i++){
for(int j=v[i];j<=m;j++){
f[j]=max(f[j],f[j-v[i]]+w[i]);
}
}
cout<<f[m]<<endl;
}
恰好装满型完全背包
int coinChange(vector<int>& coins, int amount) {
vector<int> dp(amount+1,INT_MAX);dp[0]=0;
for(auto x:coins)
for(int j=x;j<=amount;j++)
if(dp[j-x]!=INT_MAX)
dp[j]=min(dp[j],dp[j-x]+1);
return dp[amount]==INT_MAX?-1:dp[amount];
}
完全背包方案数
int change(int t, vector<int>& coins) {
vector<int> dp(t+1,0);dp[0]=1;
for(auto x:coins)
for(int j=x;j<=t;j++)
dp[j]+=dp[j-x];
return dp[t];
}
恰好装满型完全背包
int numSquares(int n) {
vector<int> dp(n+1,INT_MAX);dp[0]=0;
for(int i=1;i*i<=n;i++)
for(int j=i*i;j<=n;j++)
if(dp[j-i*i]!=INT_MAX)
dp[j]=min(dp[j],dp[j-i*i]+1);
return dp[n];
}
- 1449. 数位成本和为目标值的最大数字 1927 打印方案
爬楼梯求序列i最大值
背包+贪心策略
string largestNumber(vector<int>& cost, int target) {
auto cmp=[&](const string &a,const string &b){
if(a=="_"||b=="_") return a=="_"?b:a;
if(a.size()==b.size()) return max(a,b);
return a.size()>b.size()?a:b;
};
vector<string> f(target+1,"_");
f[0]="";
// for(int i=cost.size();i>0;i--)
// for(int j=cost[i-1];j<=target;j++)
// if(f[j-cost[i-1]]!="_")
// f[j]=cmp(f[j],f[j-cost[i-1]]+(char)(i+'0'));
//每次爬cost[i]阶楼梯，获得价值i，求序列i所对应字符串最大值
for(int i=0;i<=target;i++){
for(int j=1;j<=cost.size();j++){
if(i-cost[j-1]>=0&&f[i-cost[j-1]]!="_")
f[i]=cmp(f[i],f[i-cost[j-1]]+(char)(j+'0'));
}
}
return f[target]=="_"?"0":f[target];
}
§3.3 多重背包
物品可以重复选，有个数限制。
- 2585. 获得分数的方法数 1910
- 2902. 和带限制的子多重集合的数目 2759
§3.4 分组背包
同一组内的物品至多/恰好选一个。
- 1155. 掷骰子等于目标和的方法数 1654
- 1981. 最小化目标值与所选元素的差 2010
- 2218. 从栈中取出 K 个硬币的最大面值和 2158
四、经典线性 DP
§4.1 最长公共子序列（LCS）
一般定义f[i][j]表示对 (s[:i],t[:j])的求解结果
设f[i][j]表示text1[0:i]与text2[0:j]的公共子序列长度
int longestCommonSubsequence(string text1, string text2) {
int n=text1.size(),m=text2.size();
vector<vector<int>> f(n+1,vector<int>(m+1));
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
text1[i-1]==text2[j-1]?
f[i][j]=f[i-1][j-1]+1:
f[i][j]=max(f[i-1][j],f[i][j-1]);
return f[n][m];
}
int minDistance(string a, string b) {
int n=a.size(),m=b.size();
vector<vector<int>> f(n+1,vector<int>(m+1));
for(int i=1;i<=n;i++) f[i][0]=i;
for(int j=1;j<=m;j++) f[0][j]=j;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
a[i-1]==b[j-1]?
f[i][j]=f[i-1][j-1]:
f[i][j]=min({f[i-1][j]+1,f[i][j-1]+1,f[i-1][j-1]+2});
return f[n][m];
}
int minimumDeleteSum(string a, string b) {
int n=a.size(),m=b.size();
vector<vector<int>> f(n+1,vector<int>(m+1));
for(int i=1;i<=n;i++)
f[i][0]=f[i-1][0]+a[i-1];
for(int j=1;j<=m;j++)
f[0][j]=f[0][j-1]+b[j-1];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(a[i-1]==b[j-1])
f[i][j]=f[i-1][j-1];
else
f[i][j]=min({
f[i-1][j]+a[i-1],
f[i][j-1]+b[j-1],
f[i-1][j-1]+a[i-1]+b[j-1]
});
return f[n][m];
}
int minDistance(string a, string b) {
int n=a.size(),m=b.size();
vector<vector<int>> f(n+1,vector<int>(m+1));
for(int i=1;i<=n;i++)
f[i][0]=i;
for(int j=1;j<=m;j++)
f[0][j]=j;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(a[i-1]==b[j-1])
f[i][j]=f[i-1][j-1];
else
f[i][j]=min({f[i-1][j]+1,f[i][j-1]+1,f[i-1][j-1]+1});
return f[n][m];
}
bool isInterleave(string s1, string s2, string s3) {
int n=s1.size(),m=s2.size(),t=s3.size();
if(t!=n+m) return false;
vector<vector<int>> f(n+1,vector<int>(m+1));
f[0][0]=true;
//f i j 表示能否用前i个s1，前j个s2，交替构成前i+j个s3
for(int i=0;i<=n;i++){
for(int j=0;j<=m;j++){
if(i>0)
f[i][j] |= f[i-1][j] && s1[i-1]==s3[i+j-1];
if(j>0)
f[i][j] |= f[i][j-1] && s2[j-1]==s3[i+j-1];
}
}
return f[n][m];
}
const int MOD=1e9+7;
int numDistinct(string s, string t) {
int n=s.length(),m=t.length();
vector<vector<int>> f(n+1,vector<int>(m+1));
for(int i=0;i<=n;i++) f[i][0]=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
f[i][j]=(1LL*f[i-1][j]+(s[i-1]==t[j-1]?f[i-1][j-1]:0))%MOD;
}
}
return f[n][m];
}
- 1035. 不相交的线 1806
int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
int n=nums1.size(),m=nums2.size();
vector<vector<int>>dp(n+1,vector<int>(m+1));
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
dp[i][j]=nums1[i-1]==nums2[j-1]?
dp[i-1][j-1]+1:
max(dp[i-1][j],dp[i][j-1]);
return dp[n][m];
}
- ⭐1458. 两个子序列的最大点积 1824
int maxDotProduct(vector<int>& nums1, vector<int>& nums2) {
int n=nums1.size(),m=nums2.size();
vector<vector<int>>f(n+1,vector<int>(m+1,-1000*1000*500));
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
f[i][j]=max({
nums1[i-1]*nums2[j-1],
nums1[i-1]*nums2[j-1]+f[i-1][j-1],
f[i-1][j],
f[i][j-1],
f[i-1][j-1]
});
return f[n][m];
}
- 1092. 最短公共超序列 1977
§4.2 最长递增子序列（LIS）
经典最长递增子序列
int lengthOfLIS(vector<int>& nums) {
int n=nums.size();
vector<int> dp(n,1);
for(int i=1;i<n;i++)
for(int j=0;j<i;j++)
if(nums[j]<nums[i])
dp[i]=max(dp[i],dp[j]+1);
return *max_element(dp.begin(),dp.end());
}
设count [i]表示以nums[i]结尾的最长递增子序列的个数
int findNumberOfLIS(vector<int>& nums) {
//dp i
int n=nums.size();
vector<int> dp(n,1),count(n,1);
for(int i=1;i<n;i++)
for(int j=0;j<i;j++)
if(nums[j]<nums[i]){
if(dp[j]+1>dp[i]){
dp[i]=dp[j]+1;
count[i]=count[j];
}else if(dp[j]+1==dp[i]){
count[i]+=count[j];
}
}
int ml=*max_element(dp.begin(),dp.end()),res=0;
for(int i=0;i<n;i++){
res+=dp[i]==ml?count[i]:0;
}
return res;
}
- ⭐2826. 将三个组排序 1721
法1：LIS
int minimumOperations(vector<int>& nums) {
int n=nums.size();
vector<int> dp(n,1);
for(int i=1;i<n;i++)
for(int j=0;j<i;j++)
if(nums[j]<=nums[i])
dp[i]=max(dp[i],dp[j]+1);
return nums.size()-*max_element(dp.begin(),dp.end());
}
法2：有序修改二分
正难则反：统计能不被修改的数
修改后的数组一定有序，遍历nums查找第一个大于nums[i]所在位置，找到了则说明应该更改该位置，找不到则说明可以不修改
int minimumOperations(vector<int> &nums) {
vector<int> g;
for (int x:nums) {
auto it=upper_bound(g.begin(),g.end(),x);
if (it!=g.end()) *it = x;
else g.push_back(x);
}
return nums.size()-g.size();
}
法三：状态机dp
int minimumOperations(vector<int>& nums) {
int f[4]{};
for (int x: nums) {
f[x]++;
f[2] = max(f[2], f[1]);
f[3] = max(f[3], f[2]);
}
return nums.size() - max({f[1],f[2],f[3]});
}
- 1671. 得到山形数组的最少删除次数 1913
- 1964. 找出到每个位置为止最长的有效障碍赛跑路线 1933
- 1626. 无矛盾的最佳球队 2027
- 354. 俄罗斯套娃信封问题（二维 LIS）
- 1691. 堆叠长方体的最大高度 2172
- 960. 删列造序 III 2247
- 2407. 最长递增子序列 II 2280
- 1187. 使数组严格递增 2316
- 1713. 得到子序列的最少操作次数 2351
思维扩展：
思考题：
给定整数 k，构造一个数组 a*，使得 a* 恰好有 k 个最长递增子序列。
答：把个数记作 x。把 x 二进制拆分成 2^m1 + 2^m2 + 2^m3 + ... 例如 13 = 2^3 + 2^2 + 2^0，我们可以构造 nums=[91,91,92,92,93,93,81,82,82,83,83,71,72,73]，看成三段 [91,91,92,92,93,93], [81,82,82,83,83], [71,72,73]，每一段的最长递增子序列的个数就是前面拆分出的二进制数。这里只是举了个例子，每两段之间的的 gap 可以调大一些（比如 1000）以满足构造要求。
五、状态机 DP
一般定义 f[i][j] 表示 a[:i] 在状态j下的最优值，一般j都很小
入门案例：买卖股票
阅读建议
评论
匿名评论
隐私政策
你无需删除空行，直接评论以获取最佳展示效果