POJ - 1664 放蘋果

題目：

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

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

那末首先，當(dāng)n為0時(shí)list[0][i] = (i == 0);

其次，找遞歸式。

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

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

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

這個(gè)m-n必須為非負(fù)的，這1點(diǎn)，和0⑴背包非常相像。

準(zhǔn)確的說，這個(gè)組合題目的子問題集的拓?fù)浣Y(jié)構(gòu)和0⑴背包是1樣的。

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

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

代碼：

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