Acwing900. 整数划分[计数类dp]：完全背包解法

文章目录

• • 题目分析
  • • 完全背包解法
  • 题目链接

题目分析

完全背包解法

请复习完全背包模板完全背包dp优化内有完整标准完全背包的推导过程

状态表示： $f[i][j]$ 表示从 1~i 中选，且总和等于j 的方案数。

状态转移方程：（推导过程见下方代码）

$f[i][j]=f[i-1][j]+f[i][j-i]$

优化成一维$f[j]=f[j]+f[j-i]$（此时需要从小到大枚举）

ac代码

/* 类似完全背包问题:每个数可以取无数次f[i][j] 表示从 1~i 中选，且总和等于j 的方案数 （1）式：f[i][j] = f[i-1][j] + f[i-1][j-i]+ f[i-1][j-2*i] +...+f[i-1][j-s*i]（2）式：f[i] [j-i] = f[i-1][j-i] + f[i-1][j-2*i]+...+f[i-1][j-s*i]替换一下:（2）式替换（1）式得到状态转移方程： f[i][j] = f[i-1][j]+ f[i][j-i]空间优化一下：第一维去掉f[j] =f[j]+f[j-i] 体积从小到大循环*/#include<bits/stdc++.h> using namespace std;const int N = 1010 ,mod =1e9+7; int n; int f[N]; int main(){cin>>n;f[0] =1 ;for(int i=1;i<=n;i++){for(int j=i;j<=n;j++){f[j] = (f[j]+ f[j-i] ) % mod;}}cout<<f[n]<<endl;}

题目链接

Acwing900. 整数划分

总结

以上是生活随笔为你收集整理的Acwing900. 整数划分[计数类dp]：完全背包解法的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。