爬楼梯进阶

问ds的，不知道对不对，睡醒细看一下 #include <iostream> (30316)#include <vector> using namespace std; int climbStairs(int n, int k) { if (n == 0) return 1; if (k <= 0) return 0; vector<int> dp(n + 1, 0); dp[0] = 1; int sum = 1; // 初始窗口和为dp[0] for (int i = 1; i <= n; ++i) { dp[i] = sum; if (i >= k) sum -= dp[i - k]; sum += dp[i]; } return dp[n]; } // 优化为三个变量的版本（仅当k>3时适用） int climbStairsOptimized(int n, int k) { if (n == 0) return 1; if (k <= 0) return 0; if (k >= n) { // 当k>=n时，直接返回2^(n-1) return 1 << (n - 1); } // 初始化前k项 int prev1 = 1 << (k - 1); // dp[k] int prev2 = 1 << (k - 2); // dp[k-1] int sum = prev1 + prev2; for (int i = k + 1; i <= n; ++i) { int current = 2 * prev1 - prev2; // 递推公式 prev2 = prev1; prev1 = current; } return prev1; } int main() { int n = 5, k = 3; cout << "常规DP: " << climbStairs(n, k) << endl; // 输出13 cout << "优化后: " << climbStairsOptimized(n, k) << endl; // 输出13 return 0; }