Re: [問題] 列出一正整數之數字組合
※ 引述《rewqasdf (海的回憶)》之銘言：
: 請問輸入一正整數之後 輸出其所有組合方法
: 如
: 3=2+1=1+1+1
: 4=3+1=2+2=2+1+1=1+1+1+1
: 請問這該用什麼角度去思考問題解答
這個好像叫作無限背包
用一個陣列 dp[某數] = 幾種組合方法 記錄
不用任何數字組出 方法數 (初始)
n = 0 1 2 3 4 5 ...
dp[n] = 1 0 0 0 0 0 ...
只用 1 組合 方法數 ( dp[i] += dp[i-1] i = 1 to n )
i 可以是 i-1 加上 1 而來
n = 0 1 2 3 4 5 ...
dp[n] = 1 1 1 1 1 1 ...
只用 1,2 組合 方法數 ( dp[i] += dp[i-2] i = 2 to n )
i 可以是 i-2 加上 2 而來，方法數為：原來不用2的方法 + 用2的方法
n = 0 1 2 3 4 5 ...
dp[n] = 1 1 2 2 3 3 ...
只用 1,2,3 組合 方法數 ( dp[i] += dp[i-3] i = 3 to n )
i 可以是 i-3 加上3而來
n = 0 1 2 3 4 5 ...
dp[n] = 1 1 2 3 4 5 ...
到這裡，dp[4] = 4表示：
4 = 1+1+1+1 //只用 1 組合
= 1+2 = 2+2 //只用 1,2 組合
= 1+3 //只用 1,2,3 組合
共 4 種
其他以此類推~~
如果有說明不清楚或錯誤的
請不吝賜教~
謝謝
--
光明 的背後 是 黑暗
黑暗 的背後 還是 黑暗
由此可知 黑暗 > 光明 Q.E.D.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 124.8.140.3
討論串 (同標題文章)