C++动态规划爬楼梯实现方法解析

#include <iostream>
using namespace std;
int climbStairs(int n) {
if (n <= 1) return 1;
int dp[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];
}
int main() {
int n = 5;
cout << "爬到第 " << n << " 阶的方法数: " << climbStairs(n) << endl;
return 0;
}

#include <iostream>
using namespace std;
int climbStairs(int n) {
if (n <= 1) return 1;
int prev2 = 1; // f(i-2)
int prev1 = 1; // f(i-1)
int curr;

for (int i = 2; i <= n; ++i) {
    curr = prev1 + prev2;
    prev2 = prev1;
    prev1 = curr;
}

return prev1;
}
int main() {
int n = 6;
cout << "爬到第 " << n << " 阶的方法数: " << climbStairs(n) << endl;
return 0;
}

#include <iostream>
#include <vector>
using namespace std;
int dfs(int n, vector<int>& memo) {
if (n <= 1) return 1;
if (memo[n] != -1) return memo[n];
memo[n] = dfs(n - 1, memo) + dfs(n - 2, memo);
return memo[n];
}
int climbStairs(int n) {
vector<int> memo(n + 1, -1);
return dfs(n, memo);
}