dp类问题模版

Wanderer

2026-08-16 14:29:01

发布于：广东

5阅读

0回复

0点赞

本文不包含所有类型dp,仅包含我所学

若二维dp超空间,将第一维改成2,每个包含i的地方整体(打括号)&1计算

01背包

for(int i=1;i<=m;i++){//遍历1-m件物品
    for(int j=0;j<=t;j++){//遍历0-t的背包容量
        dp[i][j]=dp[i-1][j];//先添加不能选的情况
        if(j-w[i]>=0) dp[i][j]=max(dp[i][j],dp[i-1][j-w[i]]+v[i]);//当且仅当背包装得下第i件物品时才比较
    }
}

01背包求方案数

dp[0][0]=1;//不选也算一种方案
for(int i=1;i<=n;i++){
    for(int j=0;j<=m;j++){
        dp[i][j]=dp[i-1][j];
        if(j-w[i]>=0) dp[i][j]+=dp[i-1][j-w[i]];//方案数不需要加v[i]
    }
}

完全背包

for(int i=1;i<=m;i++){
    for(int j=0;j<=t;j++){
        dp[i][j]=dp[i-1][j];
        if(j-w[i]>=0) dp[i][j]=max(dp[i][j],dp[i][j-w[i]]+v[i]);//每件物品无限选,不同公式
    }
}

多重背包

for(int i=1;i<=n;i++){
    for(int j=0;j<=m;j++){
        dp[i][j]=dp[i-1][j];
        for(int k=1;k<=cnt[i];k++){//枚举每件物品可选次数
            if(j-k*w[i]>=0) dp[i][j]=max(dp[i][j],dp[i-1][j-k*w[i]]+k*v[i]);//都乘上选择次数k
        }
    }
}

跳跃dp(LIS)

dp[0]=1;//以第i个字符结尾的LIS
ans=1;
for(int i=1;i<=n;i++){
    dp[i]=1;
    for(int j=1;j<=i;j++){//枚举之前的字符
        if(a[j]<a[i]) dp[i]=max(dp[i],dp[j]+1);//若找到比当前字符更小的,比较LIS写入dp
        ans=max(ans,dp[i]);//每次都有新长度,一直比较
    }
}

区间dp

for(int len=2;len<=n;len++){//枚举区间长度
    for(int l=1;l+len-1<=n;l++){//枚举区间起点
        int r=l+len-1;
        dp[l][r]=INF;
        for(int k=l;k<r;k++){
            dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]+s[r]-s[l-1]);//s为前缀和数组,枚举在哪里断开可以获得最大价值
        }
    }
}

二进制枚举

for(int i=0;i<1<<n;i++){//枚举从0-2^n,枚举所有二进制状态
    int sum=0;
    for(int j=0;j<n;j++){
        if(i>>j&1) sum+=a[j];//若这一位是1,加上
    }
    if(is_prime(sum)) ans++;//实际是通过判断二进制每一位是否为1枚举所有情况
}

状态压缩dp

这个比较难,我简单喵两句
状态压缩dp,基于二进制枚举实现,它本质其实是模拟简化了全排列DFS枚举,解决非连续的问题,
比如最小异或值问题:

解法:记已排列cnt个数,通过全排列数组B,用全排列的最后一个结果与数组A的第cnt位进行异或

比如吃奶酪问题:

解法:记吃了第i个奶酪时二进制状态第i位为1,枚举为0的地方,同时开二维记录上一个奶酪位置

它们的共同点是通过枚举二进制状态的每一位,第i位为1表示第i个数被选过

//dp[i]表示二进制状态为i时匹配的最小价值
for(int i=0;i<1<<n;i++)dp[i]=INF;//初始化每一个都是最大值
	dp[0]=0;
	for(int s=0;s<1<<n;s++){//枚举二进制状态,+2^n表示第n-1位有1,二进制位数从0开始,所以循环都从0开始
		int cnt=__builtin_popcount(s);//统计这个二进制状态有几个1(被选了几个)
		for(int j=0;j<n;j++){
			if((s>>j&1)==0){//如果s的二进制中第j位是0
    			int ns=s|(1<<j);//选择这个没被选择的二进制位
    			dp[ns]=min(dp[ns],dp[s]+(a[cnt]^b[j]));//可以替换(a[cnt]^b[j]))为别的题目要求的东西,进行dp
			}
		}
	}
cout<<dp[(1<<n)-1];