03-18 01:20 北京航空航天大学 Java 发布于北京
关注
爬楼梯进阶
爬楼梯问题，求解爬楼梯的方案数，n级楼梯，每次可以爬1-k级台阶，我只想到可以将空间复杂度优化为O(k)，但快手面试官告诉我可以优化到3个变量？
求问佬们该怎么解决
求问佬们该怎么解决全部评论
牛客279059154号
中南大学 C++
问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;
}
相关推荐
米哈游公司福利 2108人发布 点赞 评论 收藏
分享
查看24道真题和解析 点赞 评论 收藏
分享