每日算法：爬楼梯问题

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?

注意： 给定 n 是一个正整数。

示例 1：

1. 输入：2
2. 输出：2
3. 解释：有两种方法可以爬到楼顶。
4. 1.1阶+1阶
5. 2.2阶

示例 2：

1. 输入：3
2. 输出：3
3. 解释：有三种方法可以爬到楼顶。
4. 1.1阶+1阶+1阶
5. 2.1阶+2阶
6. 3.2阶+1阶

解法：动态规划

动态规划(Dynamic Programming，DP)是一种将复杂问题分解成小问题求解的策略，但与分治算法不同的是，分治算法要求各子问题是相互独立的，而动态规划各子问题是相互关联的。

分治，顾名思义，就是分而治之，将一个复杂的问题，分成两个或多个相似的子问题，在把子问题分成更小的子问题，直到更小的子问题可以简单求解，求解子问题，则原问题的解则为子问题解的合并。

我们使用动态规划求解问题时，需要遵循以下几个重要步骤：

• 定义子问题
• 实现需要反复执行解决的子子问题部分
• 识别并求解出边界条件

第一步：定义子问题

如果用 dp[n] 表示第 n 级台阶的方案数，并且由题目知：最后一步可能迈 2 个台阶，也可迈 1 个台阶，即第 n 级台阶的方案数等于第 n-1 级台阶的方案数加上第 n-2 级台阶的方案数

第二步：实现需要反复执行解决的子子问题部分

1. dp[n]=dp[n−1]+dp[n−2]

第三步：识别并求解出边界条件

1. //第0级1种方案
2. dp[0]=1
3. //第1级也是1种方案
4. dp[1]=1

最后一步：把尾码翻译成代码，处理一些边界情况

1. letclimbStairs=function(n){
2. letdp=[1,1]
3. for(leti=2;i<=n;i++){
4. dp[i]=dp[i-1]+dp[i-2]
5. }
6. returndp[n]
7. }

复杂度分析：

• 时间复杂度：O(n)
• 空间复杂度：O(n)

优化空间复杂度：

1. letclimbStairs=function(n){
2. letres=1,n1=1,n2=1
3. for(leti=2;i<=n;i++){
4. res=n1+n2
5. n1=n2
6. n2=res
7. }
8. returnres
9. }

空间复杂度：O(1)

leetcode：https://leetcode-cn.com/problems/climbing-stairs/solution/pa-lou-ti-wen-ti-by-user7746o/

原文链接：https://mp.weixin.qq.com/s/W9-JRtMehbb0zy_QpJUZbw