爬楼梯问题是什么
爬楼梯问题是一个经典的动态规划问题,通常被用于学习和理解递归与动态规划的基本概念。问题的描述是:假设有一个楼梯,总共有n
级台阶,你每次可以爬1级或2级台阶,问有多少种不同的方式可以爬到楼顶。
这个问题可以通过递归、动态规划等多种方法来解决,是一道非常典型的编程题目。
问题描述
- 输入: 一个整数
n
,表示楼梯的总级数。 - 输出: 一个整数,表示到达楼顶的方法总数。
代码实现
#include <iostream>
#include <vector>using namespace std;class ClimbingStairs {
public:// 递归加记忆化的方法(自顶向下)int climbStairs(int n) {vector<int> memo(n + 1, -1);return climbStairsMemo(n, memo);}// 动态规划的方法(自底向上)int climbStairsDP(int n) {if (n <= 1) {return 1;}vector<int> dp(n + 1);dp[0] = 1;dp[1] = 1;for (int i = 2; i < n + 1; i++) {dp[i] = dp[i - 1] + dp[i - 2];}return dp[n];}private:// 带记忆化的递归函数int climbStairsMemo(int n, vector<int> &memo) {if (n <= 1) {return 1;}if (memo[n] != -1) {return memo[n];}memo[n] = climbStairsMemo(n - 1, memo) + climbStairsMemo(n - 2, memo);return memo[n];}
};int main() {ClimbingStairs solver;int n;cout << "Enter the number of steps: ";cin >> n;cout << "Number of ways to climb " << n << " steps (Memoization): " << solver.climbStairs(n) << endl;cout << "Number of ways to climb " << n << " steps (Dynamic Programming): " << solver.climbStairsDP(n) << endl;return 0;
}
思路分析
类的设计
ClimbingStairs
类封装了爬楼梯问题的解决方案,包括使用递归加记忆化(自顶向下)的方式和动态规划(自底向上)的方式。- 这种设计让不同的解法可以被独立测试和修改,并且可以轻松扩展其他解法。
- 类的设计增强了代码的模块化和可维护性,可以根据需求选择不同的解决方案。
递归加记忆化
climbStairs()
方法结合了递归和记忆化技术。这种方法通过递归来解决问题,并使用一个数组memo
来记录已经计算过的子问题结果,从而避免重复计算。- 这种方法具有自顶向下的特性,即从问题的整体逐步分解为子问题,直到解决最小的子问题。
动态规划
climbStairsDP()
方法采用动态规划的方式来解决问题。它通过迭代的方式,从最小的子问题开始,一步步累积解决更大的问题。- 动态规划的特点是自底向上构建解决方案,通过存储中间结果,避免了递归方法中的重复计算,通常效率更高。
用户界面
- 代码提供了一个简单的用户界面,通过
main()
函数获取用户输入,并展示使用两种不同方法得到的结果。 - 用户可以输入楼梯的级数
n
,然后程序将输出到达顶层的方法总数,分别展示使用记忆化递归和动态规划的方法计算的结果。