文章目錄

• • 題目分析
  • • 完全背包解法
  • 題目鏈接

題目分析

完全背包解法

請復習完全背包模板完全背包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]：完全背包解法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。