Min Cost Climbing Stairs


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)

/* 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[i1][0] + cost[i1], dp[i1][1]+cost[i1]); // taking current step dp[i][1] = dp[i1][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[k2], f[k1] )
...
f[N] = minimum cost to get to step N = cost[N] + min( f[N2], f[N1] ) # last step
finalCost = min( f[N1], f[N] )