a318. 小妮爬樓梯（總次數上限版）

Content

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

如果爬 3 階

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

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

Input

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

Output

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

Sample Input #1

4 1

Sample Output #1

Sample Input #2

5 2

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
沒有發現任何「解題報告」