a319. 小妮爬樓梯（連續次數上限版）

Content

小妮沒有大長腿，因此每次爬樓梯時她最多可以一次跨兩階。小妮發現如果他每一步可以選擇走一階、兩階，每次上樓就可以有不同的走法。但她跨兩階太多次的話腳很不舒服，於是她很好奇，如果一層樓共有 $n$ 階樓梯，而她不能連續跨兩階超過 $k$ 次，她可以有幾種不同的走法。

以範例一為例，$n = 5$，$k = 1$時有以下 6 種走法：

1+1+1+1+1
1+1+1+2
1+1+2+1
1+2+1+1
2+1+1+1
2+1+2

Input

一行輸入兩正整數 $n$ 與 $k$，分別代表階梯數量與可以連續走兩步的上限。$n \le 30$，$k \le 10$。

Output

輸出共有幾種可能的走法。題目保證答案不超過 $10^7$

Sample Input #1

5 1

Sample Output #1

Sample Input #2

20 4

Sample Output #2

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (10%): 1.0s , <1K
公開測資點#1 (10%): 1.0s , <1K
公開測資點#2 (10%): 1.0s , <1K
公開測資點#3 (10%): 1.0s , <1K
公開測資點#4 (10%): 1.0s , <1K
公開測資點#5 (10%): 1.0s , <1K
公開測資點#6 (10%): 1.0s , <1K
公開測資點#7 (10%): 1.0s , <1K
公開測資點#8 (10%): 1.0s , <1K
公開測資點#9 (10%): 1.0s , <1K

Hint ：

如果使用Python出現TLE的同學，可以嘗試在送出解答時選擇PYPY。

Tags:

遞迴

出處:

[管理者： ktlai(測試員) ]

ID	User	Problem	Subject	Hit	Post Date
沒有發現任何「解題報告」