目录
题目描述
输入输出格式
问题分析
动态规划解法
算法步骤
过题图片
代码实现
复杂度分析
题目链接
总结
题目描述
这是一个经典的动态规划问题，称为爬楼梯问题。给定一个楼梯总共有 n 阶台阶，每次可以向上爬 1 阶或者 2 阶台阶，求到达楼顶的不同方法数。
输入输出格式
-
输入：一个整数
n，表示楼梯的阶数。 - 输出：一个整数，表示到达楼顶的不同方法数。
问题分析
这个问题可以通过动态规划（DP）来解决。动态规划是一种将问题分解为更小的子问题，并通过存储这些子问题的解来避免重复计算的方法。
动态规划解法
动态规划的核心思想是：到达第 i 阶台阶的方法数等于到达第 i-1 阶台阶的方法数加上到达第 i-2 阶台阶的方法数。这是因为到达第 i 阶台阶的最后一步可以是从第 i-1 阶台阶上来的，也可以是从第 i-2 阶台阶上来的。
算法步骤
-
初始化：创建一个长度为
n+1的数组dp，用于存储到达每一阶台阶的方法数。dp[0]初始化为1，因为到达第0阶台阶（即起点）有一种方法，就是不爬。dp[1]也初始化为1，因为到达第1阶台阶有一种方法，就是直接爬一阶。 -
状态转移方程：对于
i从2到n，dp[i] = dp[i-1] + dp[i-2]。这个方程表示到达第i阶台阶的方法数是到达第i-1阶台阶和第i-2阶台阶方法数的和。 -
循环：从
2到n，依次计算dp[i]的值。 -
输出：最后，
dp[n]就是到达第n阶台阶的不同方法数。
过题图片
代码实现
java
class Solution {
public int climbStairs(int n) {
// 初始化数组，长度为 n+1，因为我们要计算到第 n 阶
int[] dp = new int[n+1];
// 到达第 0 阶和第 1 阶的方法数都是 1
dp[0] = 1;
dp[1] = 1;
// 从第 2 阶开始计算
for (int i = 2; i <= n; i++) {
// 状态转移方程
dp[i] = dp[i-1] + dp[i-2];
}
// 返回到达第 n 阶的方法数
return dp[n];
}
}复杂度分析
-
时间复杂度：
O(n)，因为我们需要遍历从2到n的所有台阶。 -
空间复杂度：
O(n)，因为我们需要一个长度为n+1的数组来存储中间结果。
递归加记忆化解法
递归的基本思想是将问题分解为更小的子问题，然后合并子问题的解来得到原问题的解。记忆化是递归中避免重复计算的一种技术，通过存储已经计算过的子问题的解，当再次遇到相同的子问题时，直接使用存储的解，而不是重新计算。
算法步骤
-
定义递归函数：定义一个递归函数
climbStairs，它接受一个参数n，表示当前的台阶数。 -
基本情况：如果
n为0或1，则返回1，因为到达第0阶或第1阶都只有一种方法。 -
记忆化存储：使用一个数组
memo来存储已经计算过的台阶数对应的方法数。 -
递归计算：对于每个台阶
i，计算到达第i阶台阶的方法数，即dp[i] = dp[i-1] + dp[i-2]。在计算之前，检查memo[i]是否已经有值，如果有，则直接返回该值；如果没有，则递归计算dp[i-1]和dp[i-2]，并将结果存储在memo[i]中。 -
返回结果：最终，
climbStairs(n)将返回到达第n阶台阶的不同方法数。 -
时间复杂度：
O(n)，因为每个台阶数只被计算一次。 -
空间复杂度：
O(n)，因为我们需要一个长度为n+1的数组来存储中间结果。递归栈的深度也是O(n)，但在最坏情况下，我们只存储了n个台阶的结果，所以空间复杂度主要由数组决定。
代码实现
java
class Solution {
private int[] memo;
public int climbStairs(int n) {
memo = new int[n + 1];
return climbStairsRecursive(n);
}
private int climbStairsRecursive(int n) {
if (n == 0 || n == 1) {
return 1;
}
if (memo[n] != 0) {
return memo[n];
}
memo[n] = climbStairsRecursive(n - 1) + climbStairsRecursive(n - 2);
return memo[n];
}
}题目链接
70. 爬楼梯 - 力扣（LeetCode）
总结
这个问题展示了动态规划的基本思想，即通过解决子问题并将结果存储起来，避免重复计算，从而提高算法的效率。通过这种方法，我们可以有效地解决爬楼梯问题。