主題
題目連結：
題目大意：
給定一正整數 ｍ （ｍ ≦ ５），代表有 ｍ 筆測試資料，每筆佔一列輸入。每列輸入給定三正整數 ｙ 、 ｉ 、 ｚ （１ ≦ ｙ ≦ ５００ ， １ ≦ ｉ ≦ ５０ ， １ ≦ ｚ ≦ １００），分別代表欲分解的數、分解出來的個數，以及數值最大的部分的數字上界。
即 ｙ ＝ ａ１ ＋ ａ２ ＋ …… ＋ ａｉ ， 且 ｚ ≧ ａ１ ≧ ａ２ ≧ …… ≧ ａｉ ≧ １ 。求有多少組 ａ１ 、 ａ２ 、 …… 、 ａｉ ？
範例輸入：
5
20 4 7
100 50 51
487 18 87
492 19 89
500 19 90
範例輸出：
13
204226
7139824136004762
20430740394679891
25985433353057732
解題思維：
首先，先看看這題以便理解以下的預設概念。
定義一個二維陣列 Ｄｉ, ｊ ， ｉ 代表要分解的數字、ｊ 代表分解出來的和之個數，而 Ｄｉ, ｊ 本身代表 ｉ 分解為 ｊ 個數字的和的方法數。
而從拉瑪努金那一題（上面連結到的題目）當中的 DP 式（不是遞迴式，因為不是由上往下（Top-Down）的求解（此為一般遞迴））稍作改動變為：
初始： Ｄ０, ０ ＝ １
for ａ ＝ １ → ｚ ：
for ｂ ＝ ｉ → ｙ ：
for ｃ ＝ １ → ｉ ：
Ｄｂ, ｃ ＝ Ｄｂ, ｃ ＋ Ｄｂ－ａ, ｃ－１
也就是我們將分解的部分之「開頭」限制在 ｚ 以下（含），並記錄每種分解長度的方法數。最後推得的 Ｄｙ, ｉ 即是所求。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
達人