題目：

劃分數

有n個無區別的物品，將他們劃分成不超過m組，求出劃分方法數模M的余數。

限制條件：

1 <= m <= n <= 1000;

2 <= M <= 10000;

輸入： 輸入 n,m,M分別代表n個物品、m個組、對M取模。

輸出： 輸出劃分方法數對M取模的余數。

樣例輸入：

4 3 1000

樣例輸出：

4

所有可能的情況都可以看作是把n劃分成m份。只是有的是取0的。

思路：

定義題目為n的m劃分數。

dp[i][j]表示 j 的 i 劃分數。

分類討論：

1.j >= i時，dp[i][j] = dp[i-1]j + dp[i][j-i]（當前位不取0，先把每一個置為1，再將剩下的j-i分下去）;

2.j < i時，dp[i][j] = dp[i-1][j]; 當前位只能取0。

注意，j的i劃分表示的意義為 j固定，i可以取到1-i。

代碼：

#include<cstdio> #include<cstring> #include<iostream> using namespace std;int dp[1010][1010];int main() { int n,m,mod;cin >> n >> m >> mod;for(int i = 1;i <= m; i++){for(int j = 0;j <= n; j++){if(j - i >= 0){dp[i][j] = (dp[i-1][j] + dp[i][j-i])%mod;}else{dp[i][j] = dp[i-1][j];}}}cout << dp[m][n] << endl;return 0; }

總結

以上是生活随笔為你收集整理的【算法】划分数 动态规划的全部內容，希望文章能夠幫你解決所遇到的問題。

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