Leetcode 746) Min Cost Climbing Stairs

13 Sep 2021 in Algorithms

Approach:

Why this problem can be solved by DP?

• Too many possibilities with brute force algo
• Optimal Substructures
• Overlapping Subproblems

My solution

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

Other Answer

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        //s(n) = min(s(n-1) + cost(n-1), s(n-2) + cost(n-2))
        int second = 0;
        int first = 0;
        
        for (int i = 2; i <= cost.length; i++){
            int minCost = Math.min(cost[i-2] + second, cost[i-1] + first);
            second = first;
            first = minCost;
        }

        return first;
    }
}