动态规划之爬楼梯

题目

假设你正在爬楼梯。需要n 步你才能到达楼顶。 每次你可以爬1 或2 个台阶。你有多少种不同的方法可以爬到楼顶呢

思路

因为每次可以爬1或者2个台阶,所以达到n阶的只能是从n-1或者n-2,也就是说达到n阶的方法等于达到n-1阶和n-2阶方法之和
以此类推,直至1阶(1种)和2阶(2种)

状态转移方程

dp[n] = dp[n-1] + dp[n-2]

最终代码

func calc(n int) int {
    if n == 1 {
        return 1
    }
    dp := make([]int, n)
    dp[0] = 1
    dp[1] = 2
    for i := 2; i <= n-1; i++ {
        dp[i] = dp[i-1] + dp[i-2]
    }
    return dp[n-1]
}