70. 爬楼梯

妖狐艹你老母 2024-03-30 15:10 73阅读 0赞

### 70. 爬楼梯 ###

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

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

##### 示例 1： #####

> 输入：n = 2  
> 输出：2  
> 解释：有两种方法可以爬到楼顶。
> 
> 1.  1 阶 + 1 阶
> 2.  2 阶

##### 示例 2： #####

> 输入：n = 3  
> 输出：3  
> 解释：有三种方法可以爬到楼顶。
> 
> 1.  1 阶 + 1 阶 + 1 阶
> 2.  1 阶 + 2 阶
> 3.  2 阶 + 1 阶

##### 提示： #####

1 <= n <= 45

#### 思路：（动态规划） ####

*  定义一个数组 dp 存储上楼梯的方法数（为了方便讨论，数组下标从 1 开始），dp\[i\] 表示走到第 i 个楼梯的方法数目。
 *  第 i 个楼梯可以从第 i-1 和 i-2 个楼梯再走一步到达，走到第 i 个楼梯的方法数为走到第 i-1 和第 i-2 个楼梯的方法数之和：  
     d p \[ i \] = d p \[ i − 1 \] + d p \[ i − 2 \] dp\[i\] = dp\[i - 1\] + dp\[i - 2\] dp\[i\]=dp\[i−1\]\+dp\[i−2\]

**改进:** 考虑到 dp\[i\] 只与 dp\[i - 1\] 和 dp\[i - 2\] 有关，因此可以只用两个变量来存储 dp\[i - 1\] 和 dp\[i - 2\]，使得原来的 O(N) 空间复杂度优化为 O(1) 复杂度。

#### 代码:(Java) ####

public class climbstars {
        
    
    	public static void main(String[] args) {
        
    		// TODO Auto-generated method stub
    		int n = 2;
    		System.out.println(climbStairs(n));
    	}
    	public static int climbStairs(int n) {
        
    		int [] dp = new int[n + 1];
    		dp[1] = 1;
    		dp[2] = 2;
    		for(int i = 3; i <= n; i++) {
        
    			dp[i] = dp[i - 1] + dp[i - 2];
    		}
    		return dp[n];
        }
    }

###### 改进： ######

public class climbstars {
        
    
    	public static void main(String[] args) {
        
    		// TODO Auto-generated method stub
    		int n = 2;
    		System.out.println(climbStairs(n));
    	}
    	public static int climbStairs(int n) {
        
    	    if (n <= 2) {
        
    	        return n;
    	    }
    	    int pre2 = 1, pre1 = 2;
    	    for (int i = 2; i < n; i++) {
        
    	        int cur = pre1 + pre2;
    	        pre2 = pre1;
    	        pre1 = cur;
    	    }
    	    return pre1;
    	}
    }

#### 运行结果： ####

![在这里插入图片描述][1e75d8d8c6634d898b8dfa0b2709b963.png]

##### 注：仅供学习参考！ #####

题目来源：[力扣.][.]

[1e75d8d8c6634d898b8dfa0b2709b963.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/a8da369bb32445708508bcaff3758c24.png
[.]: https://leetcode.cn/problems/climbing-stairs/description/