动态规划例题-爬楼梯

相关代码用golang编写

爬楼梯_力扣题目连接

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

思路

这里比较难想的是如何用计算机思维定义规律，根据题目意思我们可以简单地推导出：

第一阶方法为1，直接走一阶
第二阶方法为2，从一阶走一步，或者从0阶走两步
第三阶方法为3,1阶+1阶+1阶，1阶+2阶，2阶+1阶
...

从递推规律我们可以看出，第三阶可以用第一阶结果和第二阶结果推导出来，即第n阶可以用第n-1阶和第n-2阶的结果推导出来，这里很好理解，比如第10阶，只能从第9阶走一步或者第8阶走两步到达，那么知道第8阶和第9阶的方法数就能知道第10阶了，不断地往前递推，直到初始值第1阶和第2阶的状态，最终可以反推出结果。

有了这个基础思路后我们带入用动态规划五步曲的方法解决

• 确认dp数组及其下标含义：dp数组为到达每一阶梯的方法数集合，即dp[i]为到达第i阶的方法数

• 确定状态转移方程：i-1在跳一步就到i， i-2再跳2步就到i，所以 dp[i] = dp[i-1] + dp[i-2]，这里要注意dp[i-1]是到达i-1的方法数，这里面的每一个方法再走一步都能到i，dp[i-2]同理，里面的每一个方法再走两步都能到i，所以到i的方法数为dp[i-1]+dp[i-2]，这里数组及下标含义不能搞错，否则容易思维混淆

• 确定初始值：这里因为第0阶没有实际含义，所以我们初始值为dp[1] = 1, dp[2] = 2

• 确定遍历顺序：从3遍历到n即可，将dp数组填充，最后返回dp[n]即到达第n阶的方法数

• 举例推导论证：这里举个例子n=5，dp数组应为:[1,2,3,5,8]，在编码的时候可以打印确认

经过一番思考后，发现状态转移方程不就是菲波拉契数列吗，唯一区别在于初始值有所不同，因为第0阶没有实际含义。 不过这道题思考起来比之前直接的求菲波拉契数列可要难多了，因为他并没有直接给出状态转移方程，而是需要自己有一个推导思考过程

代码

本题的测试数据有n=0，所以编码时有特殊处理，但实际n=0应该没有含义才对

func numWays(n int) int {
    if n < 2 {
        return 1
    }


    dp := make([]int, n+1)
    dp[1] = 1
    dp[2] = 2

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

    return dp[n]
}