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

• 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;
}``````

• @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;
}``````

• 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...

• @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.

• @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);
}``````

• @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;
}``````

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