动态规划 爬楼梯问题进阶

输入：一共有n阶楼梯，一次最多可以爬k阶，求一共有多少种总步数不超过50的爬法？ （若不可能达成则输出0）
例：假设有300阶 一次最多3阶 则不可能总次数不超过50,所以输出0

想请问这题怎么写 谢谢！ ！

令dp[i][s]表示通过s步走到第i个阶梯的方法数目。
dp[i][s] = dp[i-1][s-1] + dp[i-2][s-1] + ... + dp[i-k][s-1]
表面上，总共三层循环，时间复杂度是o(N*50*K)

注意到上述表达式本质是个滑窗，如果k很大，那么最后一层循环可以均摊到o(1)，总的时间复杂度是o(N*50).

坐蹲一个标准答案，刚好最近在刷动规，提供一个我的思路

这道题其实和lc 70的思路以类似， 如果是n阶，需要一个array 来记录到每一阶走法的总和

因此前k 次的走法可以提前得到，对于每阶i，走法的总和是1+2+…+i

到第k+1阶的时候，可以根据前k阶的走法推算出总和，例如这一步如果走了1步，那到k+1阶的步数总和是 arr[k]+1, 如果这一步走的是两步，那arr[k+1]=arr[k-2]+1，以此类推，

推算到最后一阶，就可以看之前n-k 到n-1哪些少于49步

不知道我说的对不对，求轻拍🤣

wisdompeak2 发表于 2021-03-27 15:10:37
令dp表示通过s步走到第i个阶梯的方法数目。
dp = dp + dp + ... + dp
表面上，总共三层循环，时间复杂度是o(N*50*K)

你好 谢谢你的回覆，我想请问这样要如何初始化呢？ base case 跟没有限制步数是一样的吗

wisdompeak2 发表于 2021-03-27 15:10:37
令dp表示通过s步走到第i个阶梯的方法数目。
dp = dp + dp + ... + dp
表面上，总共三层循环，时间复杂度是o(N*50*K)

好方法！想请教如果用这种方法初始化，是不是dp[51][n+1]

一开始可以知道dp[1][1]到dp[1][k]的值，然后推第二行，也就是可以推出第二步的值？

zxc97 发表于 2021-3-28 06:46
你好 谢谢你的回覆，我想请问这样要如何初始化呢？ base case 跟没有限制步数是一样的吗

对于DP的初始化技巧，就是观察你的general转移方程的下标
在之前的那个表达式：dp[i] = dp[i-1][s-1] + dp[i-2][s-1] + ... + dp[i-k][s-1]
我们发现当i<k以及s==0的时候，有些项的下标是负数，意味着这些dp[i]需要单独处理或者初始化。
具体的初始化方法一般根据的题境。
比如dp[x][0]表示到达第x层用0步，显然都是0
比如dp[k-1]，显然应该将原转移方程去掉最后一项。