[問題] 分割數問題 (n相同物放入m相同箱, 可空)
問題(Question)：
這是"培養與鍛鍊 程式設計的邏輯腦"(一本書)中第71頁的題目:
請求出將n個無法互相區別的物品分割成m個以下的方法之總數，
以及除以M之後的餘數。
原題目的文字敘述不是很好懂，
可以將題目理解為:
將n個相同物放入m個相同箱，允許有空箱的方法數s，
s除以M的餘數即為答案。
餵入的資料(Input)：
n = 4
m = 3
M = 10000
預期的正確結果(Expected Output)：
4
錯誤結果(Wrong Output)：
9
程式碼(Code)：(請善用置底文網頁, 記得排版)
好讀版: http://codepad.org/52BGIUYa
#include <iostream>
#include <fstream>
using namespace std;
// file
fstream fin("sample.in");
// constant
const static int MAX_N = 1000;
const static int MAX_M = 1000;
// input
int n, m, k;
// output
int dp[MAX_M + 1][MAX_N + 1];
int main()
{
// input
fin >> n >> m >> k;
// solve
dp[0][0] = 1;
for (int i = 1; i <= m; ++i)
for (int j = 0; j <= n; ++j)
dp[i][j] = (j >= i) ? (dp[i - 1][j] + dp[i][j - 1]) % k : dp[i - 1][j];
// output
cout << dp[m][n] << endl;
return 0;
}
補充說明(Supplement)：
這章是在交 dp 解，
code 是參考書本上的 code，稍微修改，
但演算法內容不變。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 211.74.49.80
※ 編輯: redsmallbo 來自: 211.74.49.80 (01/23 21:12)
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1 之 2 篇)：
C_and_CPP 近期熱門文章
PTT數位生活區 即時熱門文章