# Min Cost Climbing Stairs

• You can mention the Bottom-Up solution as Approach #2

``````public int minCostClimbingStairs(int[] cost) {
int a=0, b=0, c;
for(int i=2;i<=cost.length;i++){
c = Math.min(b+cost[i-1], a+cost[i-2]);
a = b;
b = c;
}
return c;
}``````

• Thanks. Based on above, here is solution for Golang

import "math"
func minCostClimbingStairs(arr []int) int {
a := 0
b := 0
c := 0

``````for i := 2; i <= len(arr); i++ {

c = int(math.Min(float64(arr[i-2] + a), float64(arr[i-1] + b)))
a = b
b = int(c)
}

return c
``````

}

• ## Recursion

Time: O(2^N), Space: O(1)

``````def minCostClimbingStairs(self, cost):
def recurse(index, cost):
if index >= len(cost):
return 0
else:
return cost[index] + min(recurse(index+1, cost), recurse(index+2, cost))

return min(recurse(0, cost), recurse(1, cost))
``````

## DP: Recursion with memoization

Time: O(N), Space: O(N)

``````def minCostClimbingStairs(self, cost):
hashmap = dict()

def recurse(index, cost):
if index in hashmap:
return hashmap[index]
elif index >= len(cost):
value = 0
else:
value = cost[index] + min(recurse(index+1, cost), recurse(index+2, cost))
hashmap[index] = value
return value

return min(recurse(0, cost), recurse(1, cost))
``````

## Bottom up with only 2 variables

Time: O(N), Space: O(1)

``````    f1 = 0
f2 = 0
for x in reversed(cost):
minCostFromThisStep = x + min(f1, f2)
f2 = f1
f1 = minCostFromThisStep
return min(f1, f2)
``````

• Given sample [10, 15, 20]

#1 loop: i=1, f0=15, f1=15, f2=0
#2 loop: i=0 f0=10, f1=10, f2=15

Return 10.

• ``````// swift4
class Solution {
func minCostClimbingStairs(_ cost: [Int]) -> Int {

var dp = Array(repeating: 0, count: cost.count + 1)
dp[0] = cost[0]
dp[1] = cost[1]

for i in 2..<cost.count {
dp[i] = min(dp[i-1], dp[i-2]) + cost[i]
}

return min(dp[cost.count - 1], dp[cost.count - 2])
}
}
``````

• //a more simple solution without using any extra variables

public int minCostClimbingStairs(int[] cost) {

``````    for(int i=2;i<=cost.length-1;i++){
cost[i]=cost[i]+Math.min(cost[i-1],cost[i-2]);
}

return Math.min(cost[cost.length-1],cost[cost.length-2]);

}``````

• what's the difference between inverse and reverse?

• /* Simple DP solution - at each step we make a decision to take this step or not. If we take current step, then we take the min of taking and not taking previous step and add the current cost.
If we don't take the current step, then we have to take the previous step - so directly get the value from taking the previous step
Finally return the min of taking and not taking the final step*/
class Solution {
public int minCostClimbingStairs(int[] cost) {
int n = cost.length;
int[][] dp = new int[n+1][2];
for(int i = 1; i < dp.length; i++) {

``````            dp[i][0] = Math.min(dp[i-1][0] + cost[i-1], dp[i-1][1]+cost[i-1]); // taking current step
dp[i][1] = dp[i-1][0]; // not taking current step

}
return Math.min(dp[n][0], dp[n][1]);
}
``````

}

• I think there is no need to compute in reverse. I tested. The Python solution code works even without using "reversed".

The final output is the summation of the visited steps. The optimal path going forward visits the same set of steps as the optimal return (backward) path does. This is due to symmetry of the enter and exit rules. Also, the order does not matter for the summation.

Enter at any of the first two steps. Exit from any of the last two steps.

However, as for me, it is more intuitive to compute in forward order.
f[1] = minimum cost to get to step 1 = cost[1]
f[2] = minimum cost to get to step 2 = cost[2]
f[3] = minimum cost to get to step 3 = cost[3] + min( f[1], f[2] )
...
f[k] = minimum cost to get to step k = cost[k] + min( f[k-2], f[k-1] )
...
f[N] = minimum cost to get to step N = cost[N] + min( f[N-2], f[N-1] ) # last step
finalCost = min( f[N-1], f[N] )

• "there is no need to compute in reverse,
dp[0] = cost[0]
dp[1] = cost[1] " ,
this solution is wrong, at least when there are just two steps in cost, for example, cost = [10,15],
dp[1] = 10, not 15

• there is wrong solution and test cases when I submit it says
Input:
[0,0,1,1]
Output:
0
Expected:
1

it should be 0 cost, isn't it?

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