爬楼梯的最小费用动态规划
提问于 2019-12-07 11:34:26
我正试图解决以下有关leetcode的问题：
On a staircase, the i-th step has some non-negative cost cost[i] assigned (0 indexed).
Once you pay the cost, you can either climb one or two steps.
You need to find minimum cost to reach the top of the floor, and you can either start
from the step with index 0, or the step with index 1.我的解决方案如下：
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
return helper(cost, cost.size() - 1);
}
int helper(vector<int>& cost, int currStair) {
static vector<double> minCost(cost.size(), 0);
minCost[0] = cost[0];
minCost[1] = cost[1];
if (minCost[currStair] > 0) {
return minCost[currStair];
}
return minCost[currStair] = min(helper(cost, currStair - 1), helper(cost, currStair - 2)) + cost[currStair];
}
};当我尝试提交时，我会得到以下运行时错误。为什么？
AddressSanitizer: heap-buffer-overflow on address 0x603000000008 at pc 0x0000004089af bp 0x7ffdd02dcaa0 sp 0x7ffdd02dca98
编辑的解决方案：
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
return helper(cost, cost.size() - 1);
}
int helper(vector<int>& cost, int currStair) {
if (currStair < 0 || cost.size() <= 1) {
return 0;
}
static vector<double> minCost(cost.size(), 0);
minCost[0] = cost[0];
minCost[1] = cost[1];
if (minCost[currStair] > 0) {
return minCost[currStair];
}
minCost[currStair] = min(helper(cost, currStair - 1), helper(cost, currStair - 2)) + cost[currStair];
return min(minCost[cost.size()-1], minCost[cost.size()-2]);
}
};如您所见，我在代码的末尾做了一些更改。
回答 1
Stack Overflow用户
回答已采纳
发布于 2019-12-07 12:00:07
这个问题是递归缺少的基本情况。在每个递归调用中，currStair总是减少-1或-2，但是没有条件检查它是否低于0并切断递归，从而导致像minCost[-1]这样的非法内存访问。
增加先决条件
if (currStair < 0) return 0;你又回到了轨道上，尽管算法仍然有正确性问题需要解决。
这里有一个提示，可以帮助你摆脱困境：
的说明说：“您需要找到到达楼层顶部的最小成本，可以从索引0的步骤开始，也可以从索引1的步骤开始。”
。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/59229495
复制
社区富文本编辑器全新改版！诚邀体验～
全新交互，全新视觉，新增快捷键、悬浮工具栏、高亮块等功能并同时优化现有功能，全面提升创作效率和体验
腾讯云开发者
