Short O(1) space, Ruby/Python/Java/C++


  • 0

    Keep track of the optimal sums for the latest two steps.

    Ruby version:

    def min_cost_climbing_stairs(cost)
      cost.reduce([0]) { |s, c| [c + s.min, s[0]] }.min
    end
    

    Python version:

    def minCostClimbingStairs(self, cost):
        return min(reduce(lambda s, c: [c + min(s), s[0]], cost, [0]))
    

    For-loop version:

    def minCostClimbingStairs(self, cost):
        s = [0]
        for c in cost:
            s = c + min(s), s[0]
        return min(s)
    

    Java version:

    public int minCostClimbingStairs(int[] cost) {
        int a = 0, b, min = 0;
        for (int c : cost) {
            b = a;
            a = c + min;
            min = Math.min(a, b);
        }
        return min;
    }
    

    C++ version:

    int minCostClimbingStairs(vector<int>& cost) {
        int a = 0, b, result = 0;
        for (int c : cost) {
            b = a;
            a = c + result;
            result = min(a, b);
        }
        return result;
    }

  • 1
    A

    @StefanPochmann Further shortening it, using trick I learned from you.

    public int minCostClimbingStairs(int[] cost) {
        int a = 0, b, min = 0;
        for (int c : cost)
            min = Math.min(b=a, a=c+min);
        return min;
    }

  • 0

    I do not fully understand the meaning of using s represents "the latest two steps" ...
    Assume s[0] represents the optimal sum of passing cost[i], and s[1] for cost[i+1].

    Why does the next s[1] = cost[i] + min(s[1], s[0])? I feel min(s[1] + cost[i+1], s[0] + cost[i]) is more reasonable...


  • 0

    @aayushgarg Nice. I guess I was still in Python mode, where assignments aren't expressions.

    @waigx s[0] is the sum for the latest step, and s[-1] is the sum for the step one step before, not after (so for i-1, not i+1). And the sum includes the cost for the step itself. So for the new step, you add its cost c to the cost of getting there, which is min(s) because you must have gotten there from one of the latest two steps.


  • 1

    @StefanPochmann

    Your java version can use just 2 variables:

    public int minCostClimbingStairs(int[] cost) {
        int a = 0, b = 0;
        for(int c : cost)
            b = Math.min(a, (a = b)) + c;
        return Math.min(a, b);
    }

  • 1

    @tyuan73 Nice as well, although I'm not a fan of the double Math.min. But we can do it this way (which is really just @aayushgarg's without the actually unused b):

    public int minCostClimbingStairs(int[] cost) {
        int a = 0, min = 0;
        for (int c : cost)
            min = Math.min(a, a=c+min);
        return min;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.