Leetcode70

题目标签

动态规划

解题思路

与509.斐波那契数相似，由于每次只能向上走[1]步或者[2]步，所以第[n]阶楼梯只能由第[n-1]阶楼梯或者第[n-2]阶楼梯向上走一步或者两步到达，故只要将到达第[n-1]阶楼梯或和第[n-2]阶楼梯的不同方法相加即是到达第[n]阶楼梯所有的不同方法数

AC代码

1
2
3
4
5
6
7
8

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

• ← Previous Post
• Next Post →