Java Solution Using DP


  • 3
    R
    class Solution {
        public int minCostClimbingStairs(int[] cost) {
            int [] mc = new int[cost.length + 1];
            mc[0] = cost[0];
            mc[1] = cost[1];
            
            for(int i = 2; i <= cost.length; i++){
                int costV = (i==cost.length)?0:cost[i];
                mc[i] = Math.min(mc[i-1] + costV, mc[i-2] + costV);
            }
            return mc[cost.length];
        }
    }
    

  • 1
    B

    Similar idea.

    class Solution {
        public int minCostClimbingStairs(int[] cost) {
            int len = cost.length();
            int[] dp = new int[len];
            dp[len - 1] = cost[len - 1];
            dp[len - 2] = cost[len - 2];
            for (int i = len - 3; i >= 0; i--)
                dp[i] = Math.min(dp[i + 1], dp[i + 2]) + cost[i];
            return Max.min(dp[0], dp[1]);
        }
    }
    

  • 0
    D

    Java O(n) time, O(1) space:

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

Log in to reply
 

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