位於維基百科:知識問答/存檔/結構式討論的話題

想不到爬樓梯問題還有這種惱人的變形，不過蠻有趣的，所以來和大家分享、請益(因為我算不出來)與討論。謝謝！

从12阶回溯，若3步则到9阶，若2步需要再走3步避开8阶抵达7阶，所以问题变成：

计算到0->7/9阶 & 12->20阶的所有可能方法，并加以组合

所以請問閣下的算式與答案是？

dp=[0]*25

dp[2]=1

dp[3]=1

#从4爬到10

#爬到i级的路径数量=i-2和i-3阶数量之和

for i in range(4,10):

dp[i]=dp[i-2]+dp[i-3]

print(i,dp[i])

dp[10]=dp[7]#10阶只能走7阶

dp[11]=dp[9]#11阶只能走9阶

for i in range(12,21):

dp[i]=dp[i-2]+dp[i-3]

输出：

4 1

5 2

6 2

7 3

8 4->这阶不走

9 5

……10 3

……11 5

12 8

13 8

14 13

15 16

16 21

17 29

18 37

19 50

20 66

最后有66种走法

可是該考試機構公布的答案是32。

32是排列组合，(dp[7]+dp[9])*dp[20-12]=32，忘记必须要走12阶了

补充一下才会对

dp[13]=0

dp[14]=dp[12]=8

dp[15]=dp[12]+dp[13]=8

dp[20]

=dp[17]+dp[18]

=dp[14]+dp[15]+dp[15]+dp[13]+dp[14]

=8+8+8+0+8=32

好像排列组合弄不出来

2+2+2+3+3

走兩階三次到第六階時，改走三階(閃過8)站在地9階，在走三階踩上12階。