Leet Code 322. Coin Change

 https://leetcode.com/problems/coin-change/

package pep.Day86;

import java.util.Arrays;

public class LeetCode_322_Coin_Change {

    public static void main(String[] args) {
        int[] coins = {1, 2, 5};
        int amt = 11;

        System.out.println(coinChangeRecursion(coins, amt));
        System.out.println(coinChangeMemo(coins, amt, new int[amt + 1]));
        System.out.println(coinChangeTabulation(coins, amt, new int[amt + 1]));
    }

    public static int coinChangeRecursion(int[] coins, int amt) {
        if (amt < 0)
            return -1;
        if (amt == 0)
            return 0;
        int min = Integer.MAX_VALUE;

        // sab coins ko mauka denge
        for (int coin : coins) {
            int x = coinChangeRecursion(coins, amt - coin);
            if (x >= 0 && x < min) {
                min = x + 1;    // count for current coin
            }
        }

        return min == Integer.MAX_VALUE ? -1 : min;
    }

    public static int coinChangeMemo(int[] coins, int amt, int[] dp) {
        if (amt < 0)
            return -1;
        if (amt == 0)
            return 0;

        if (dp[amt] != 0)
            return dp[amt];

        int min = Integer.MAX_VALUE;

        // sab coins ko mauka denge
        for (int coin : coins) {
            int x = coinChangeMemo(coins, amt - coin, dp);
            if (x >= 0 && x < min) {
                min = x + 1;    // count for current coin
            }
        }

        return dp[amt] = min == Integer.MAX_VALUE ? -1 : min;
    }

    public static int coinChangeTabulation(int[] coins, int amt, int[] dp) {
        Arrays.fill(dp, (int) 1e9);
        dp[0] = 0;
        for (int i = 0; i <= amt; i++) { 
            for (int coin : coins) {

                if (i - coin >= 0)
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);

            }
        }

        if (dp[amt] != (int) 1e9)
            return dp[amt];
        return -1;

    }

}

Leet Code 377. Combination Sum IV

https://leetcode.com/problems/combination-sum-iv/

package pep.Day85;

public class LeetCode_377_Combination_Sum_IV {
    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        int target = 4;
        System.out.println(combinationSum4(nums, target));
    }

    public static int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target + 1];

        dp[0] = 1;
        for (int i = 0; i < dp.length; i++) {
            for (int coin : nums) {
                if (coin <= i) {
                    dp[i] += dp[i - coin];
                }
            }
        }

        return dp[target];
    }
}

Leet Code 354. Russian Doll Envelopes

https://leetcode.com/problems/russian-doll-envelopes/

package pep.Day85;

import java.util.Arrays;

public class LeetCode_354_Russian_Doll_Envelopes {
    public static void main(String[] args) {
        int[][] envelopes = {{5, 4}, {6, 4}, {6, 7}, {2, 3}};
        System.out.println(maxEnvelopes(envelopes));
    }

    public static class Pair implements Comparable<Pair> {
        int width;
        int height;

        Pair(int width, int height) {
            this.width = width;
            this.height = height;
        }

        @Override
        public int compareTo(Pair o) {
            if (this.width != o.width) {
                // increasing width
                return this.width - o.width;
            } else {
                // decreasing on the basis of height
                return o.height - this.height;
            }
        }
    }

    public static int maxEnvelopes(int[][] envelopes) {
        int n = envelopes.length;
        Pair[] arr = new Pair[n];

        for (int i = 0; i < n; i++) {
            arr[i] = new Pair(envelopes[i][0], envelopes[i][1]);
        }

        Arrays.sort(arr);

        // LIS on height
        int maxLength = 1;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);

        for (int endIndex = 1; endIndex < n; endIndex++) {
            for (int startIndex = 0; startIndex < endIndex; startIndex++) {
                if (arr[startIndex].height < arr[endIndex].height) {
                    dp[endIndex] = Math.max(dp[endIndex], dp[startIndex] + 1);
                }
            }

            if (dp[endIndex] > maxLength)
                maxLength = dp[endIndex];
        }

        return maxLength;
    }
}

Leet Code 673. Number of Longest Increasing Subsequence

https://leetcode.com/problems/number-of-longest-increasing-subsequence/

package pep.Day85;

import java.lang.reflect.Array;
import java.util.Arrays;

public class LeetCode_673_Number_of_Longest_Increasing_Subsequence {
    public static void main(String[] args) {

        int[] nums = {1, 3, 5, 4, 7};
        System.out.println(findNumberOfLIS(nums));
    }

    public static int findNumberOfLIS(int[] nums) {
        int maxLength = 1, maxCount = 1;

        int n = nums.length;
        int[] dp = new int[n];
        int[] count = new int[n];

        Arrays.fill(dp, 1);
        Arrays.fill(count, 1);

        for (int endIndex = 1; endIndex < n; endIndex++) {
            for (int startIndex = 0; startIndex < endIndex; startIndex++) {
                if (nums[startIndex] < nums[endIndex]) {
                    // aab mujhe sabse bade wala cheye

                    if (dp[startIndex] + 1 > dp[endIndex]) {
                        dp[endIndex] = dp[startIndex] + 1;
                        count[endIndex] = count[startIndex];
                    } else if (dp[startIndex] + 1 == dp[endIndex]) {
                        // iss baar dono ki values same ho gae, toh sirf count me new wala add kr do
                        count[endIndex] += count[startIndex];
                    }
                }
            }
            if (dp[endIndex] > maxLength) {
                maxLength = dp[endIndex];
                maxCount = count[endIndex];
            } else if (dp[endIndex] == maxLength) {
                maxCount = count[endIndex];
            }

        }

        return maxCount;
    }
}

Longest Bitonic Subsequence

https://www.geeksforgeeks.org/longest-bitonic-subsequence-dp-15/

package pep.Day85;

import java.lang.reflect.Array;
import java.util.Arrays;

public class Longest_Bitonic_Subsequence {
    public static void main(String[] args) {

        int[] nums = {1, 2, 5, 3, 2};
        System.out.println(LongestBitonicSequence(nums));
    }

    public static int LongestBitonicSequence(int[] nums) {
        int n = nums.length;
        // increasing subsequence
        int[] LIS = new int[n];
        // decreasing subsequence
        int[] LDS = new int[n];

        LIS_LeftToRight(nums, LIS);
        LIS_RightToLeft(nums, LDS);

        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans = Math.max(ans, LIS[i] + LDS[i] - 1);
        }

        return ans;
    }

    private static void LIS_RightToLeft(int[] nums, int[] dp) {
        Arrays.fill(dp, 1);
        int n = nums.length;
        for (int endIndex = n - 1; endIndex >= 0; endIndex--) {
            for (int startIndex = endIndex + 1; startIndex < n; startIndex++) {
                if (nums[startIndex] < nums[endIndex]) {
                    dp[endIndex] = Math.max(dp[startIndex] + 1, dp[endIndex]);
                }
            }
        }
    }

    private static void LIS_LeftToRight(int[] nums, int[] dp) {
        Arrays.fill(dp, 1);
        int n = nums.length;
        for (int endIndex = 0; endIndex < n; endIndex++) {
            for (int startIndex = 0; startIndex < endIndex; startIndex++) {
                if (nums[startIndex] < nums[endIndex]) {
                    dp[endIndex] = Math.max(dp[startIndex] + 1, dp[endIndex]);
                }
            }
        }
    }

}