爬楼梯问题是什么
爬楼梯问题是一个经典的动态规划问题，通常被用于学习和理解递归与动态规划的基本概念。问题的描述是：假设有一个楼梯，总共有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，然后程序将输出到达顶层的方法总数，分别展示使用记忆化递归和动态规划的方法计算的结果。
