※ 引述《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