爬楼梯

• • 1. 动态规划思路
  • 2. 解决方法
  • 3. 代码

题目简述：爬 n 阶楼梯才能到达楼顶，每次可以爬 1 或 2 个台阶。

1. 动态规划思路

动态规划是一种常见的解决问题的方法，它通过将大问题分解成更小的子问题，并利用子问题的解来解决大问题。

在爬楼梯的问题中，可以将问题分解成两个子问题：爬到第 n-1 阶楼梯和爬到第 n-2 阶楼梯。因为每次可以爬 1 或 2 个台阶，所以爬到第 n 阶楼梯的方法数就是爬到第 n-1 阶楼梯的方法数加上爬到第 n-2 阶楼梯的方法数。

2. 解决方法

使用一个数组 dp 来存储爬到每一阶楼梯的方法数，其中 dp[i] 表示爬到第 i 阶楼梯的方法数。

初始时，dp[0] = 1（爬到第 0 阶楼梯只有一种方法），dp[1] = 1（爬到第 1 阶楼梯只有一种方法）。然后可以通过递推关系 dp[i] = dp[i-1] + dp[i-2] 来计算 dp 数组的其他值。最后，返回 dp[n] 即可得到爬到楼顶的总方法数。

3. 代码

空间复杂度O(n)

public int climbStairs(int n) {int[] dp = new int[n+1];dp[0] = 1;dp[1] = 1;for (int i = 2;i<=n;++i){dp[i] = dp[i-1] + dp[i-2];}return dp[n];}

空间复杂度O(1)

public int climbStairs(int n) {int pre1 = 1;// 前一阶楼梯的方法数int pre2 = 1;// 前两阶楼梯的方法数for (int i = 2;i<=n;++i){int current = pre1+pre2;pre2 = pre1;pre1 = current;}return pre1;}