離散數學-遞迴 習題求解

C(1)=2 (1元可買2種物品)
C(2)=3+2*2=7(2元3種or 1元又1元2*2種)
C(3)=1+7*2+2*3(3元1種+ 2元又1元7*2種+ 1元又2元2*3種)
考慮最後一件物品的價格,共有3種case
case1: 最後一件為3元(1種),then前面有n-3元C(n-3)種,共有C(n-3)*1種
case2: 最後一件為2元(3種),then前面有n-2元C(n-2)種,共有C(n-2)*3種
case3: 最後一件為1元(2種),then前面有n-1元C(n-1)種,共有C(n-1)*2種
故C(n)=C(n-3)+3C(n-2)+2C(n-1)

2010-04-24 17:52:08 補充：
題意中買東西的順序是有差別的,否則C(2)不會是7
因此1+3與3+1不同!

TO天助心清
這樣算會重複喔
例如
我C(n-3)中已經買了A(1元的) 在花3元買B
和我C(n-1)中已經買了B(3元的) 在花1元買A
結論是一樣的 但是你至少算了兩次