leetcode --- 三步问题（DP）

laijh · · 693 次点击 · · 开始浏览

这是一个创建于的文章，其中的信息可能已经有所发展或是发生改变。

第一次，站长亲自招 Gopher 了>>>

三步问题
 leetcode-golang

问题

有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶或3阶。实现一种方法，计算小孩有多少种上楼梯的方式。结果可能很大，你需要对结果模1000000007。

示例1:
输入：n = 3
输出：4
说明: 有四种走法

示例2:
输入：n = 5
输出：13

提示:
n范围在[1, 1000000]之间

解题思路

分析：设跳到i阶的方式有dp[i]种方式，那么跳往dp[i]的所有情况为

第 i-3 阶跳 3 阶，dp[i-3]种方式
第 i-2 阶跳 2 阶，dp[i-2]种方式
第 i-1 阶跳 1 阶，dp[i-1]种方式

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

疑问：为什么 i-3 阶跳到 i-2 阶不算一种？因为这种情况已经归属到跳往 i-2 阶的情况中了，也就是在 dp[i-2] 内

当i很大时，dp[i]之前出现越界？要怎么规避这个问题？

因为需要对结果进行取模操作，也就是 dp[i] % 1000000007，dp[i] % 1000000007 = (dp[i-3] + dp[i-2] + dp[i-1]) % 1000000007
dp[i] % 1000000007 = (x1 + z1 * 1000000007) % 1000000007 = x1
(dp[i-3] + dp[i-2] + dp[i-1]) % 1000000007 = (dp[i-3] % 1000000007 + dp[i-2] % 1000000007 + dp[i-1] % 1000000007) % 1000000007

代码

func waysToStep(n int) int {
    dp := make([]int, n+4)

    dp[0], dp[1], dp[2], dp[3] = 0, 1, 2, 4
    for i := 4;i <= n;i++ {
        dp[i] = (dp[i-1] % 1000000007 + dp[i-2] % 1000000007 + dp[i-3] % 1000000007) % 1000000007
    } 
    return dp[n] % 1000000007
}

有疑问加站长微信联系（非本文作者）