关注
问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;
}
查看原帖
点赞 评论
相关推荐
点赞 评论 收藏
分享
点赞 评论 收藏
分享
点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 字节求职进展汇总 #
689946次浏览 6973人参与
# 机械人与华为的爱恨情仇 #
98568次浏览 891人参与
# 携程求职进展汇总 #
194008次浏览 1514人参与
# 牛友故事会 #
223630次浏览 4628人参与
# 小米提前批笔试难吗 #
28154次浏览 297人参与
# 文科生还参加今年的春招吗 #
7261次浏览 82人参与
# 满帮集团求职进展汇总 #
2071次浏览 52人参与
# 中兴求职进展汇总 #
561178次浏览 2581人参与
# 实习必须要去大厂吗? #
76089次浏览 1142人参与
# 求职你最看重什么? #
49596次浏览 302人参与
# 工作两年想退休了 #
95044次浏览 960人参与
# 讲讲我的真实离职原因 #
30602次浏览 357人参与
# 正在实习的你,有转正机会吗? #
347179次浏览 2770人参与
# 大厂无回复,继续等待还是奔赴小厂 #
97615次浏览 824人参与
# 读研or工作,哪个性价比更高? #
36132次浏览 516人参与
# 扒一扒那些奇葩实习经历 #
15037次浏览 164人参与
# 牛友打假中心 #
18931次浏览 1018人参与
# 德州仪器求职进展汇总 #
2378次浏览 75人参与
# 找工作,你会甘心进小厂还是猛冲大厂 #
261773次浏览 2998人参与
# bilibili求职进展汇总 #
43651次浏览 459人参与
# 你觉得机械有必要实习吗 #
39730次浏览 391人参与