寻找最小楼梯成本的动态编程问题的错误答案 [英] Wrong answer to dynamic programming problem of finding minimum stair cost

问题描述

我正在尝试解决Leetcode上的以下问题：

I am trying to solve the following problem on Leetcode:

在楼梯上，第i步有一些非负数指定了费用 cost [i] （索引为0）。

支付费用后，您可以爬一两个步骤。
您需要找到到达最低层的最低成本，并且可以从索引为0的步骤开始，也可以从索引为1的步骤开始。

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.

到目前为止，这是我的解决方案。我认为我没有正确考虑到我可以从0楼梯或1楼梯开始的事实，而且我不确定该怎么做。

This is my solution so far. I believe I'm not correctly taking into account the fact that I can start at stair 0, or stair 1, and I'm not sure how to do so.

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 (currStair < 0 || cost.size() <= 1) {
            return 0;
        }

        if (minCost[currStair] > 0) {
            return minCost[currStair];
        }

        return minCost[currStair] = min(helper(cost, currStair - 1), helper(cost, currStair - 2)) + cost[currStair];

    }
};

推荐答案

这是非常正确的主意，但我认为

This is very much the right idea, but I think it's sort of a conflation of top-down and bottom-up approaches.

由于问题告诉我们我们可以从第0步或第1步开始，因此我认为这样做更直观从头到尾遍历 cost 数组-您仍可以在执行操作时使用自上而下的递归DP方法。这样可以更轻松地区分从第0步或第1步开始。您的代码返回的最终解决方案始终是 minCost [minCost.size（）-1] ，而这没有考虑到这一点。

Since the problem tells us we can start on steps 0 or 1, I think it's more intuitive to work through the cost array from front to back--you can still use a top-down recursive DP approach as you're doing. This makes it easier to distinguish between starting at the 0th or 1st step. The final solution that's returned by your code is always minCost[minCost.size()-1] which doesn't take this into account.

使用静态向量会使函数变为非幂等，因此它将在第二次运行时保留陈旧的值。就Leetcode而言，这不会影响正确性，因为它似乎为每个测试用例创建了一个新的类实例。但是，这似乎与上述一般性误解有关；初始化0和1索引并没有像您想的那样设置正确的基本案例（这是您采用自下而上的方法设置基本案例的方式）。

Using a static vector makes the function non-idempotent, so it'll persist stale values on a second run. This doesn't impact correctness as far as Leetcode is concerned because it seems to create a new instance of your class per test case. Nonetheless, it seems related to the above general misunderstanding; initializing 0 and 1 indices isn't setting a correct base case as you may think (this is how you'd set the base case in a bottom-up approach).

请牢记这一点，从第一个台阶解决问题，然后向前走到最后一个台阶。非静态地初始化缓存矢量，然后从索引0递归地填充缓存。缓存将处理2 ⁿ 分支因数，将复杂度降低为线性，最终结果将是从楼梯0或1开始的成本的最小值。问题将输入的 cost 向量限制为 2< = cost.size（ ）是一个很大的提示；我们知道 minCost [0] 和 minCost [1] 始终可以在没有先决条件的情况下进行选择。

With this in mind, approach the problem from the first stair and walk forward to the last. Initialize the cache vector non-statically, then populate the cache recursively from index 0. The prohibitive 2ⁿ branching factor will be handled by the cache, reducing the complexity to linear, and the final results will be the min of the cost of starting at stair 0 or 1. The fact that the problem constrains the input cost vector to 2 <= cost.size() is a big hint; we know minCost[0] and minCost[1] will always be available to choose between without preconditions.

另一个要点是，使用0作为空缓存标志可能会在填充有零的巨大矢量上超时。由于我们需要区分未设置索引和0，因此应使用-1作为标志来指示未设置缓存索引。

Another minor point is that using 0 as the empty cache flag could time out on huge vectors filled with zeroes. Since we need to distinguish between an unset index and a 0, we should use -1 as the flag to indicate an unset cache index.

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        vector<int> minCost(cost.size(), -1);
        helper(cost, 0, minCost);
        return min(minCost[0], minCost[1]);
    }

    int helper(vector<int>& cost, int currStair, vector<int>& minCost) {
        if (currStair >= cost.size()) return 0;
        else if (minCost[currStair] >= 0) {
            return minCost[currStair];
        }

        return minCost[currStair] = cost[currStair] +
               min(helper(cost, currStair + 1, minCost), 
                   helper(cost, currStair + 2, minCost));
    }
};

这篇关于寻找最小楼梯成本的动态编程问题的错误答案的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！