Leet Code 746. Min Cost Climbing Stairs

 

import java.util.Arrays;

public class LeetCode_846_Min_Cost_Climbing_Stairs {
    public static void main(String[] args) {
        int[] cost = {10, 15, 20};
        minCostClimbingStairs(cost);
    }

    public static void minCostClimbingStairs(int[] cost) {
        int n = cost.length;

        System.out.println(Math.min(recursion(cost, n - 1), recursion(cost, n - 2)));

        int[] dp = new int[n + 1];
        Arrays.fill(dp, -1);
        System.out.println(Math.min(recursionMemo(cost, n - 1, dp), recursionMemo(cost, n - 2, dp)));

        Arrays.fill(dp, -1);
        System.out.println(Math.min(recursionTabulation(cost, n - 1, dp), recursionTabulation(cost, n - 2, dp)));

    }

    public static int recursion(int[] cost, int n) {
        if (n < 0)
            return 0;
        else if (n == 0 || n == 1)
            return cost[n];

        int left = recursion(cost, n - 1);
        int right = recursion(cost, n - 2);
        return Math.min(left, right) + cost[n];

    }

    public static int recursionMemo(int[] cost, int n, int[] dp) {
        if (n < 0)
            return 0;
        else if (n == 0 || n == 1)
            return dp[n] = cost[n];

        if (dp[n] != -1) return dp[n];

        int left = recursionMemo(cost, n - 1, dp);
        int right = recursionMemo(cost, n - 2, dp);
        return dp[n] = Math.min(left, right) + cost[n];

    }

    public static int recursionTabulation(int[] cost, int N, int[] dp) {

        for (int n = 0; n <= N; n++) {
            if (n < 0)
                continue;
            else if (n == 0 || n == 1) {
                dp[n] = cost[n];
                continue;
            }

            //if (dp[n] != -1) return dp[n];

            int left = dp[n - 1];//recursionTabulation(cost, n - 1, dp);
            int right = dp[n - 2];//recursionTabulation(cost, n - 2, dp);
            dp[n] = Math.min(left, right) + cost[n];
        }
        return dp[N];
    }
    
}