Min Cost Climbing Stairs


  • 0

    Click here to see the full article post


  • 0
    A

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

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

    }


  • 0
    T

    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)
    

  • 0
    D

    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.

    The answer is 15.


  • 0
    U
    // 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])
        }
    }
    

  • 0
    A

    //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]);
    
    }

  • 0
    D

    what's the difference between inverse and reverse?


  • 0
    A

    /* 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]);
    }
    

    }


  • 0
    S

    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] )


  • 0
    A

    "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


  • 0
    Z

    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?


Log in to reply
 

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