POJ - 1664 放蘋果

題目：

這個題目自然是遞歸，但是否是所有人的遞歸式都是1樣的。

假定本題對應(yīng)的答案是list[n][m]，n,m非負，

那末首先，當n為0時list[0][i] = (i == 0);

其次，找遞歸式。

如果這n個盤子里面，存在空盤子，那末去掉它，就變成“把m個相同的蘋果放入n⑴個相同的盤子”這個子問題了。

否則，每一個盤子都最少有1個蘋果，那末去掉這n個蘋果，就變成“把m-n個蘋果放入n個相同的盤子”這個子問題了。

所以，遞歸式就是list[n][m]=list[n⑴][m]+list[n][m-n]

這個m-n必須為非負的，這1點，和0⑴背包非常相像。

準確的說，這個組合題目的子問題集的拓撲結(jié)構(gòu)和0⑴背包是1樣的。

也就是說，如果這個題目只有1組m,n，那末本題就不需要2維數(shù)組，只需要1維數(shù)組，便可利用0⑴背包的空間緊縮方法算出結(jié)果。詳情點擊打開我的博客（0⑴背包）

下面的代碼，雖然沒有這樣，但是初始化的順序卻是1樣的。

代碼：

生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學(xué)習(xí)有所幫助,可以手機掃描二維碼進行捐贈