Dynamic Programming.txt

1) sort and array using recursion
2)DP question-> https://www.youtube.com/watch?v=VT4bZV24QNo
3)Heavy weight knapsack
4) Just add all the questions from eclipse after doing all questions


SOLUTIONS OF THESE QUESTIONS ARE EITHER ON GFG OR ON LEETCODE.
---------------------------------------DYNAMIC PROGRAMMING-----------------------------------------

1. 0-1 Knapsack / Book Shop (CSES)
public static int KnapsackTD(int[] wt, int[] price, int vidx, int cap, int[][] strg) {
//		if (cap < 0) {
//			return Integer.MAX_VALUE;
//		}

		if (vidx == wt.length) {
			return 0;
		}
		if (strg[vidx][cap] != 0) {
			return strg[vidx][cap];
		}
		int ans = 0;
		int in = 0;
		if (cap >= wt[vidx]) {
			in = KnapsackTD(wt, price, vidx + 1, cap - wt[vidx], strg) + price[vidx];
		}
		int ex = KnapsackTD(wt, price, vidx + 1, cap, strg);
		ans = Math.max(in, ex);

		strg[vidx][cap] = ans;
		return ans;

	}
->Bottom Up Approach->https://www.youtube.com/watch?v=bUSaenttI24&list=WL&index=57&t=21s

 public static int KnapsackBU(int[]wt,int[]val,int n,int cap){
        int[][]dp=new int[n+1][cap+1];
        
        for(int i=1;i<=n;i++){
            for(int j=1;j<=cap;j++){
                if(j>=wt[i-1]) //player can bat or weight can be added.
                {   int rCap=j-wt[i-1];
                    if(dp[i-1][rCap]+val[i-1]>dp[i-1][j]){
                       dp[i][j]=dp[i-1][rCap]+val[i-1];  //took i-1 in val array also bcz of the storage, draw matrix to know
                    }else{
                       dp[i][j]=dp[i-1][j]; 
                    }
                    
                }else{
                    dp[i][j]=dp[i-1][j]; //player can't bat or weight can't be added
                }
            }
        }
        return dp[n][cap];
    }

----------------- -------------------------------------------------------------------------------
2. Matrix Chain Multiplication
public static int MCMTD(int[] matrix, int si, int ei, int[][] strg) {
		if (ei - si == 1) {
			return 0;
		}

		if (strg[si][ei] != 0) {
			return strg[si][ei];
		}
		int ans = Integer.MAX_VALUE;
		for (int k = si + 1; k <= ei - 1; k++) {
			int fp = MCMTD(matrix, si, k, strg);
			int sp = MCMTD(matrix, k, ei, strg);
			int sw = matrix[si] * matrix[k] * matrix[ei];
			int overall = fp + sp + sw;
			if (overall < ans) {
				ans = overall;
			}

		}
		strg[si][ei] = ans;
		return ans;
	}
------------------------------------------------------------------------------------------------
3. Edit Distance
    public int EditdistanceTD(String s1, String s2, int[][] strg) {

		if (s1.length() == 0 || s2.length() == 0) {
			return Math.max(s1.length(), s2.length());
		}

		if (strg[s1.length()][s2.length()] != -1) {
			return strg[s1.length()][s2.length()];
		}

		char ch1 = s1.charAt(0);
		char ch2 = s2.charAt(0);
		String ros1 = s1.substring(1);
		String ros2 = s2.substring(1);
		int ans = 0;
		if (ch1 == ch2) {
			ans = EditdistanceTD(ros1, ros2, strg);
		} else {
			int ins = EditdistanceTD(ros1, s2, strg) + 1;
			int del = EditdistanceTD(s1, ros2, strg) + 1;
			int rep = EditdistanceTD(ros1, ros2, strg) + 1;

			ans = Math.min(ins, Math.min(del, rep));
		}
		strg[s1.length()][s2.length()] = ans;
		return ans;
	}
------------------------------------------------------------------------------------------------
4. Catalan Number to find no. of Bst's
	public static int Catalannumberofbsts(int n, int[] strg) {
		if (n <= 1) {
			return 1;
		}
		if (strg[n] != 0) {
			return strg[n];
		}
		int sum = 0;
		for (int i = 1; i <= n; i++) {
			int left = Catalannumberofbsts(i - 1, strg);
			int right = Catalannumberofbsts(n - i, strg);
			int total = left * right;
			sum += total;

		}

		strg[n] = sum;
		return sum;
	}

->Catalan Number
public static void CatalanNumber(int n) {
		int dp[] = new int[n + 1];
		dp[0] = 1;
		dp[1] = 1;
		for (int i = 2; i < dp.length; i++) {
			for (int j = 0; j < i; j++) {
				dp[i] += dp[j] * dp[i - j - 1];
			}
		}
		System.out.println(dp[n]);
	}
------------------------------------------------------------------------------------------------
5. Longest Common Subsequence 
 public  int LCSTD(String s1, String s2, int[][] strg) {
		if (s1.length() == 0 || s2.length() == 0) {
			return 0;
		}

		if (strg[s1.length()][s2.length()] != -1) {
			return strg[s1.length()][s2.length()];
		}
		char ch1 = s1.charAt(0);
		char ch2 = s2.charAt(0);
		String ros1 = s1.substring(1);
		String ros2 = s2.substring(1);
		int ans = 0;
		if (ch1 == ch2) {
			ans = LCSTD(ros1, ros2, strg) + 1;
		} else {
			int fp = LCSTD(s1, ros2, strg);
			int sp = LCSTD(ros1, s2, strg);

			ans = Math.max(fp, sp);
		}
		strg[s1.length()][s2.length()] = ans;
		return ans;
	}
*)LCS Space Optimised->
public int LCsSpaceOptimised(String s1, String s2) {
		int[] strg = new int[s2.length() + 1];
		int prev = 0; //for taking ros1,ros2 in acccount because we can't get this from 1d array

		for (int i = s1.length() - 1; i >= 0; i--) {
			prev = strg[strg.length - 1];
			for (int j = strg.length - 2; j >= 0; j--) {
				int backup = strg[j];
				char ch1 = s1.charAt(i);
				char ch2 = s2.charAt(j);
				int ans = 0;
				if (ch1 == ch2) {
					ans = prev + 1;
				} else {
					int fp = strg[j + 1];
					int sp = strg[j];
					ans = Math.max(fp, sp);
				}
				prev = backup;
				strg[j] = ans;
			}
		}
		return strg[0];
	}
------------------------------------------------------------------------------------------------
6. Palindromic Partitions/cuts 
->BLog because we did some further optimization in this question  
https://leetcode.com/problems/palindrome-partitioning-ii/discuss/1267844/JAVA-or-Recursion-%2B-Memoization-or-Optimized-Matrix-Chain-Multiplication-Approach-with-Code-(MCM)

public int PalindromicpartitionscutTD(String str, int si, int ei, int[][] strg) {
		if (strg[si][ei] != -1) {
			return strg[si][ei];
		}

		if (Ispalindrome(str, si, ei)) {
			return 0;
		}

		int ans = Integer.MAX_VALUE;
		for (int k = si; k <= ei - 1; k++) {
			if (Ispalindrome(str, si, k)) {
				int min = 1 + PalindromicpartitionscutTD(str, k + 1, ei, strg);
				ans = Math.min(min, ans);
			}

		}
		strg[si][ei] = ans;
		return ans;
	}
------------------------------------------------------------------------------------------------
7. Wildcard Matching
public boolean WildcardpatternTD(String s1, String s2, int[][] strg) {
		if (s1.length() == 0 && s2.length() == 0) {
			return true;
		}
		if (s1.length() != 0 && s2.length() == 0) {
			return false;
		}

		if (s1.length() == 0 && s2.length() != 0) {
			for (int i = 0; i < s2.length(); i++) {
				if (s2.charAt(i) != '*') {
					return false;
				}
			}
			return true;

		}

		if (strg[s1.length()][s2.length()] != 0) {
			return strg[s1.length()][s2.length()] == 2 ? true : false;
		}

		char ch1 = s1.charAt(0);
		char ch2 = s2.charAt(0);
		String ros1 = s1.substring(1);
		String ros2 = s2.substring(1);

		boolean ans = false;
		if (ch1 == ch2 || ch2 == '?') {
			ans = WildcardpatternTD(ros1, ros2, strg);
		} else if (ch2 == '*') {
			boolean op1 = WildcardpatternTD(s1, ros2, strg);
			boolean op2 = WildcardpatternTD(ros1, s2, strg);
			ans = op1 || op2;
		}
		strg[s1.length()][s2.length()] = (ans) ? 2 : 1;
		return ans;
	}
------------------------------------------------------------------------------------------------
8. Board Path/Dice Combination (CSES) 
public static int boardpathTD(int curr, int end, int[] strg) {
		if (curr == end) {
			return 1;
		}
		if (curr > end) {
			return 0;
		}
		if (strg[curr] != 0) {
			return strg[curr];
		}
		int count = 0;
		for (int dice = 1; dice <= 6; dice++) {
			if (curr + dice <= end) {
				count += boardpathTD(curr + dice, end, strg);
			}
		}
		strg[curr] = count;

		return count;
	} 
------------------------------------------------------------------------------------------------
9. Coin Change/ CoinCombinationII (CSES)
->Using 2 states
public  long CoinCombinationII(int[] coin, int val, int n) {
		long[][] dp = new long[n + 1][val + 1];

		for (int i = 1; i <= n; i++) {
			for (int sum = 0; sum <= val; sum++) {
				if (sum == 0) {
					dp[i][sum] = 1;
				} else {
					long op1 = (coin[i-1] > sum) ? 0 : dp[i][sum - coin[i-1]];
					long op2 = (i == 1) ? 0 : dp[i - 1][sum];
					dp[i][sum] = (op1 + op2);
				}
			}
		}
		return dp[n][val];
	}
Using One state only->
 public int CoinCombinationII(int[] coin, int val, int n) {
		int[] dp = new int[val + 1];
		dp[0] = 1; // if no sum then we can leave this and this could be a way 
		for (int i = 0; i < n; i++) {
			for (int j = coin[i]; j < dp.length; j++) {
				dp[j] += dp[j - coin[i]];

			}
		}
		return dp[val];
	}

CoinCombinationI (Permutation) (CSES) 
public static long CoinCombinationI(int[] coin, int val, int n) {
		long[] dp = new long[val + 1];
		dp[0] = 1; // if no sum then we can leave and this could be a way
		for (int sum = 1; sum <= val; sum++) {
			for (int coin_value : coin) {
				if (coin_value <= sum)
					dp[sum] = (dp[sum] + dp[sum - coin_value]) % MOD;
			}
		}
		return dp[val];
	}
------------------------------------------------------------------------------------------------
10. Minimizing Coins/ Coin change on leetcode
 public int coinChange(int[] coins, int amount) {
        Arrays.sort(coins);
        int[]dp=new int[amount+1];
        
        Arrays.fill(dp,amount+1);
        dp[0]=0;
        for(int i=0;i<=amount;i++){
            for(int j=0;j<coins.length;j++){
                if(coins[j]<=i){
                    dp[i]=Math.min(dp[i],1+dp[i-coins[j]]);
                }else
                    break;
            }
        }
        return (dp[amount]>amount)?-1:dp[amount];        
    }
------------------------------------------------------------------------------------------------
11. Subset Sum Problem/ Partition Equal Subset Sum
public boolean SubsetSum(int nums[], int vidx, int sum, int total,HashMap<String,Boolean>state) {
		String current=vidx+""+sum;
        if (state.containsKey(current)) {
			return state.get(current);
		}
		if (total == 2 * sum) {
			return true;
		}

		if (sum > total || vidx >= nums.length)
			return false;

		boolean ans=SubsetSum(nums,vidx+1,sum+nums[vidx],total,state)||
            SubsetSum(nums,vidx+1,sum,total,state);

		state.put(current,ans);
		return ans;
	}

------------------------------------------------------------------------------------------------
12. Target Sum Subset ->(Kind of 0-1 Knapsack Problem)
https://www.pepcoding.com/resources/online-java-foundation/dynamic-programming-and-greedy/target-sum-subsets-dp-official/ojquestion

 public static boolean TargetSumSubsets(int[]arr,int n,int tar){
      boolean[][]dp=new boolean[n+1][tar+1];
      dp[0][0]=true; //because empty set can be make sum 0 only.
      for(int i=1;i<=n;i++){
        for(int j=0;j<=tar;j++){
            if(j==0){
                dp[i][j]=true;
                continue;
            }
            if(j<arr[i-1]){
                dp[i][j]=dp[i-1][j];
            }else{
                boolean op1=dp[i-1][j];
                boolean op2=dp[i-1][j-arr[i-1]];
                dp[i][j]=op1||op2;
            }
        }
      }
      return dp[n][tar];
  }
------------------------------------------------------------------------------------------------
13. Friends Pairing Problem
 public static long FriendsPairing(int n) {
		if (n == 0)
			return 0;
		if (n == 1)
			return 1;
		if (n == 2)
			return 2;

		long dp[] = new long[n + 1];

		int M = 1000000007;

		dp[1] = 1;
		dp[2] = 2;

		for (int i = 3; i < dp.length; i++) {
			dp[i] = (dp[i - 1] + ((i - 1) * dp[i - 2]) % M) % M;
		}
		
		return dp[n];
	}
------------------------------------------------------------------------------------------------
14. Binomial Coefficient Problem (nCr)
Formula Used->   C(n, r) = C(n-1, r-1) + C(n-1, r)
 C(n, 0) = C(n, n) = 1
 public static int nCr(int n, int r) {
		int C[][] = new int[n + 2][r + 2];

		for (int i = 0; i <= n; i++) {
			for (int j = 0; j <= Math.min(i, r); j++) {
				if (j == 0 || j == i)
					C[i][j] = 1;
				else
					C[i][j] = (C[i - 1][j] % MOD + (C[i - 1][j - 1]) % MOD) % MOD;

			}
		}
		return C[n][r];
	}


------------------------------------------------------------------------------------------------
15. Permutation Coefficient Problem (nPr)
Formula Used->P(n, k) = P(n-1, k) + k* P(n-1, k-1)
P(n,0)=1;

static int permutationCoeff(int n,
                                int k)
    {
        int P[][] = new int[n + 2][k + 2];
     
        // Calculate value of Permutation
        // Coefficient in bottom up manner
        for (int i = 0; i <= n; i++)
        {
            for (int j = 0;
                j <= Math.min(i, k);
                j++)
            {
                // Base Cases
                if (j == 0)
                    P[i][j] = 1;
     
                // Calculate value using previosly
                // stored values
                else
                    P[i][j] = P[i - 1][j] +
                            (j * P[i - 1][j - 1]);
     
                // This step is important
                // as P(i,j)=0 for j>i
                P[i][j + 1] = 0;
            }
        }
        return P[n][k];
    }
------------------------------------------------------------------------------------------------
16. Grid Paths (CSES)
 public static int GridPaths(int[][] grid, int n) {
		int[][] strg = new int[n + 1][n + 1];

		for (int row = n; row >= 1; row--) {
			for (int col = n; col >= 1; col--) {
				if (grid[row - 1][col - 1] == 1) {
					strg[row][col] = 0;
					continue;
				}
				if (row == n && col == n) {
					strg[row][col] = 1;
				} else {
					int op1 = (col == n) ? 0 : strg[row][col + 1];
					int op2 = (row == n) ? 0 : strg[row + 1][col];
					strg[row][col] = (op1 + op2) % MOD;
				}
			}
		}
		return strg[1][1];
	}
------------------------------------------------------------------------------------------------
17. Removing Digits (CSES)
	private static int RemovingDigits(int n) {
		int[] dp = new int[n + 1];
		for (int i = 1; i <= n; i++) {
			char[] arr = new String("" + i).toCharArray();
			int res = Integer.MAX_VALUE;
			for (int j = 0; j < arr.length; j++) {
				if (arr[j] != '0')
					res = Math.min(dp[i - (arr[j] - '0')] + 1, res);
			}
			dp[i] = res;
		}
		return dp[n];
	}
------------------------------------------------------------------------------------------------
18. Longest Common Subsequence 3D (with 3 Strings)
public static int LCS3(String s1, String s2, String s3, int[][][] strg) {
		if (s1.length() == 0 || s2.length() == 0 || s3.length() == 0) {
			return 0;
		}

		if (strg[s1.length()][s2.length()][s3.length()] != -1) {
			return strg[s1.length()][s2.length()][s3.length()];
		}
		char ch1 = s1.charAt(0);
		char ch2 = s2.charAt(0);
		char ch3 = s3.charAt(0);
		String ros1 = s1.substring(1);
		String ros2 = s2.substring(1);
		String ros3 = s3.substring(1);
		int ans = 0;
		if (ch1 == ch2 && ch2 == ch3) {
			ans = LCS3(ros1, ros2, ros3, strg) + 1;
		} else {
			int options[] = new int[6];
			options[0] = LCS3(s1, ros2, ros3, strg);
			options[1] = LCS3(ros1, s2, ros3, strg);
			options[2] = LCS3(ros1, ros2, s3, strg);
			options[3] = LCS3(s1, s2, ros3, strg);
			options[4] = LCS3(s1, ros2, s3, strg);
			options[5] = LCS3(ros1, s2, s3, strg);
			ans = 0;
			for (int val : options)
				ans = Math.max(ans, val);

		}
		strg[s1.length()][s2.length()][s3.length()] = ans;
		return ans;
	}
------------------------------------------------------------------------------------------------
19. Array Desciption (CSES)
Intuition->
Think about the DP definition DP[i][x], it says number of valid Arrays A[1..i] such that ith element = x.
If A[i] = 0 then I can change to it to x and then I can obtain some valid arrays where the ith Element is X.
If A[i] is already equal to x then also some valid arrays exist where the ith element is x but if it's not possible to have x at the ith position then no valid array exist where the ith element = x

	public static long ArrayDescription(int n, int m, int[] arr) {
		int[][] dp = new int[n + 1][m + 2];

		for (int i = 1; i <= n; i++) {
			for (int x = 1; x <= m; x++) {
				if (i == 1) { // 1 size array.
					if (arr[i] == 0 || arr[i] == x) {
						dp[i][x] = 1;
					} else
						dp[i][x] = 0;
				} else {
					if (arr[i] == 0 || arr[i] == x) {
			dp[i][x] = ((dp[i - 1][x - 1] + dp[i - 1][x]) % MOD + dp[i - 1][x + 1]) % MOD;
					} else {
						dp[i][x] = 0;
					}
				}
			}
		}

		long ans = 0;
		for (int x = 1; x <= m; x++) {
			ans = (ans + dp[n][x]) % MOD;
		}
		return ans;
	}
-----------------------------------------------------------------------------------------------
Important Note: In questions like longest subsequence or substring , try to find out the ans which ends at current element. 
------------------------------------------------------------------------------------------------
20. Longest Increasing Subsequence 
Intuition-> at each index we are finding the LIS which ends with arr[idx]. at last we are finding the max in the dp array.
Iterative->

public int lengthOfLIS(int[] nums) {
        int n=nums.length;
        int[]dp=new int[n];
        
        int omax=0;
        
        for(int i=0;i<n;i++){
            int max=0;
            for(int j=0;j<i;j++){
                if(nums[i]>nums[j]){
                    if(dp[j]>max){
                        max=dp[j];
                    }
                }
            }
            dp[i]=1+max;
            if(dp[i]>omax){
                omax=dp[i];
            }
        }
        return omax;        
    }

NlogN Approach->https://www.youtube.com/watch?v=nf3YG4CnTbg / Kartik Arora 
->Here, we are observing that if there are two candidates which are helping to extend the subsequence with same values for eg (10) (4) 6 11 then we show smaller candidate as it will help in extending more length in future just in 
                         (1)  (1) 
this case if we chose 10 then it get extended to 10 11 length (2), but if we chose element 4 then it get extended to 4 6 11 length (3), this also depicts that at a particular length there will be only 1 length corresponding to it.
And also that sorted values contain sorted advantages

That's the intuition behind this complexity.

	public static int LISOptimised(int[] nums) {
		int n = nums.length;
		int dp[] = new int[n];
		dp[0] = 1;
		TreeMap<Integer, Integer> candidate = new TreeMap<Integer, Integer>();
		candidate.put(nums[0], dp[0]);
		for (int i = 1; i < n; i++) {
			dp[i] = 1 + getBestCandidate(candidate, nums[i]);
			insertCandidate(candidate, nums[i], dp[i]);
		}

		int max = 0;
		for (int i = 0; i < dp.length; i++) {
			max = Math.max(max, dp[i]);
		}
		return max;
	}

	private static int getBestCandidate(TreeMap<Integer, Integer> candidate, int val) {
		if (candidate.lowerKey(val) == null) {
			return 0;
		}
		return candidate.get(candidate.lowerKey(val));
	}

	public static void insertCandidate(TreeMap<Integer, Integer> candidate, int k, int v) {

		if (candidate.getOrDefault(k, 0) >= v)
			return;

		candidate.put(k, v);
		Integer key = candidate.higherKey(k);


		while (key != null && candidate.get((int) key) <= v) { // means key giving
																// less advantage
																// but is more in //
																// value
			Integer temp = key;
			key = candidate.higherKey((int) temp);
			candidate.remove(temp);
		}
	}
-------------------------
Easiest Approach-> NlogN
public static int LISOptimised(int[] nums) {
		int n = nums.length;
		int dp[] = new int[n + 1];
		dp[0] = Integer.MIN_VALUE;

		for (int i = 1; i <= n; i++) {
			dp[i] = Integer.MAX_VALUE;
		}

		for (int i = 0; i < n; i++) {
			int idx = UpperBound(dp, 0, n, nums[i]);
			if (idx >= dp.length)
				continue;

			//nums[i]>dp[idx-1] checked for strictly increasing seq.

]			if (nums[i] > dp[idx - 1] && nums[i] < dp[idx]) {  //though nums[i] always<dp[i] 
				dp[idx] = nums[i];		//because we found upper bound	
			}
		}
		int ans = 0;
		for (int i = n; i > 0; i--) {
			if (dp[i] != Integer.MAX_VALUE) {
				ans = i;
				break;
			}
		}

		return ans;
	}

	public static int UpperBound(int[] arr, int lo, int hi, int val) {
		int ans = 0;
		while (lo <= hi) {
			int mid = lo + (hi - lo) / 2;
			if (arr[mid] <= val) {
				lo = mid + 1;
				ans = mid;
			} else {
				hi = mid - 1;
			}
		}
		return ans + 1;
	}

------------------------------------------------------------------------------------------------
21. Unbounded Knapsack 
    public static int unboundedKnapsack(int[] wt, int[] price, int W) {
		int[] dp = new int[W + 1];
		for (int i = 0; i < wt.length; i++) {
			for (int j = 1; j <=W; j++) {
				if(j>=wt[i]) {
					dp[j]=Math.max(dp[j], price[i]+dp[j-wt[i]]);
				}
			}
		}
		return dp[W];
	}
	public static int unboundedKnapsack(int[] wt, int[] price, int cap, int vidx, int[][] dp) {
		if (cap < 0) {
			return 0;
		}
		if (vidx == price.length)
			return 0;
		if (dp[vidx][cap] != -1)
			return dp[vidx][cap];

		int in = 0, ex = 0;
		if (cap >= wt[vidx]) {
			in = unboundedKnapsack(wt, price, cap - wt[vidx], vidx, dp) + price[vidx];
		}
		ex = unboundedKnapsack(wt, price, cap, vidx + 1, dp);
		int ans = Math.max(in, ex);
		dp[vidx][cap] = ans;
		return ans;
	}
------------------------------------------------------------------------------------------------
22. Longest Repeated Subsequence
Logic-> find lcs of string with itself keeping in mind that both equal characters have diff indx
Memoization->
   public int LRS(String str, int i, int j, int[][] dp) {
		if (i == 0 || j == 0) {
			return 0;
		}

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

		int ans = 0;
		if (i != j && str.charAt(i - 1) == str.charAt(j - 1)) {
			ans = 1 + LRS(str, i - 1, j - 1, dp);
		} else {
			int fp = LRS(str, i - 1, j, dp);
			int sp = LRS(str, i, j - 1, dp);
			ans = Math.max(fp, sp);
		}
		dp[i][j] = ans;
		return ans;
	}
Tabulation->
    public int LRSBU(String str) {
		int[][] dp = new int[str.length() + 1][str.length() + 1];

		for (int row = str.length() - 1; row >= 0; row--) {
			for (int col = str.length() - 1; col >= 0; col--) {

				char ch1 = str.charAt(row);
				char ch2 = str.charAt(col);
				int ans = 0;
				if (ch1 == ch2 && row != col) {
					ans = dp[row + 1][col + 1] + 1;
				} else {
					int fp = dp[row][col + 1];
					int sp = dp[row + 1][col];

					ans = Math.max(fp, sp);
				}
				dp[row][col] = ans;

			}
		}
		return dp[0][0];
	}
------------------------------------------------------------------------------------------------
23. Longest Common Substring
Logic-> compare all prefixes of string 1 with prefixes of string 2 and find longest common suffix (which is ultimately longest common substring)
*some substring is always a suffix of some prefix , this is the intuition
->Dry run bottom up approach for better understanding.

 int longestCommonSubstr(String s1, String s2, int n, int m){
     int [][]dp=new int[n+1][m+1];
     int max=0;
     
     for(int i=1;i<=n;i++){
         for(int j=1;j<=m;j++){
            char c1=s1.charAt(i-1);
            char c2=s2.charAt(j-1);
            if(c1!=c2){
                dp[i][j]=0;
            }else{
                dp[i][j]=1+dp[i-1][j-1]; //common sufffix
            }
            if(dp[i][j]>max)
                max=dp[i][j];
        }
     }
     return max;
    }

Memoization->
------------------------------------------------------------------------------------------------
24. Count Palindromic Substrings 
logic-> We make a 2d array and there row represent the starting character and column represents the ending character. to check whether string is palidrome or not, we just have to check for 2 conditions. 
i) starting and ending character should be same,
ii) internal string that is (i+1,j-1)string should be palidrome.
if there is n gap between characters then there is n+1 characters

public int countSubstrings(String s) {
        boolean[][]dp= new boolean[s.length()][s.length()];
        
        int count=0;
        for(int gap=0;gap<s.length();gap++){
            for(int i=0,j=gap;j<s.length();i++,j++){//Every slide starts from first row but ends 
                 if(gap==0){                       	       //with last column 
                     dp[i][j]=true;
                 }else if(gap==1){
                     if(s.charAt(i)==s.charAt(j))
                         dp[i][j]=true;
                 }else{
                     if(s.charAt(i)==s.charAt(j) && dp[i+1][j-1])
                         dp[i][j]=true;
                 }                                         
                if(dp[i][j])
                    count++;
                }    
            }        
        return count;
    }
------------------------------------------------------------------------------------------------
25.a) Count Palidromic Subsequences
*) str= c1+m+c2 
->sq(str)= c1(yes/no)+ sq(m) + c2(yes/no)
->sq(c1 m)=c1(yes/no) +sq(m)
->sq(m c2)=sq(m)+c2(yes/no)
->sq(m)=sq(m) 

sq(c1m)->{_sq(m)}-->cn1,  {c1sq(m)_}-->cn3
sq(mc2)->{sq(m)_}-->cn1,  {sq(m)c2}-->cn2

count(c1+m+c2)-> cn1{_sq(m)_} , cn2{_sq(m)c2} , cn3{c1sq(m)_} , cn4{c1sq(m)c2}

if(c1==c2){
count=cn1+cn2+cn3+cn4
count=cn1+cn2+cn3+(cn1+1)
count=1+(cn1+cn2)+(cn1+cn3)
count=1+count(mc2)+count(c1m)
}else if(c1!=c2){
count=cn1+cn2+cn3+0
count=cn1+cn2+cn3
count=cn1+cn2+cn3+cn1-cn1
count=(cn1+cn2)+(cn1+cn3)-count(m){c1}
count=count(mc2)+count(c1m)-count(m)
}

 public long CountPalidromicSubsequences(String str) {
		long[][] dp = new long[str.length()][str.length()];

		for (int gap = 0; gap < str.length(); gap++) {
			for (int i = 0, j = gap; j < str.length(); i++, j++) {
				if (gap == 0) {
					dp[i][j] = 1;
				} else if (gap == 1) {
					dp[i][j] = (str.charAt(i) == str.charAt(j)) ? 3 : 2;
				} else {
					if (str.charAt(i) == str.charAt(j)) {
							(prefix)             (suffix)
						dp[i][j] = ((dp[i][j - 1] + dp[i + 1][j]) % MOD + 1) % MOD;
					} else {
						dp[i][j] = ((dp[i][j - 1] + dp[i + 1][j]) % MOD - dp[i + 1][j - 1]+MOD) % MOD;
					}
				}
			}
		}
		return dp[0][str.length() - 1];
	}

25.b) Count distinct Palidromic subsequences ->https://www.youtube.com/watch?v=fvYlinirmFg
-> here we used set theory (inclusion - exclusion principle) ans also some explaination from above question
(1u2u3)=1+2+3-(1i2)-(2i3)-(1i3)+(1i2i3)

Using above explaination->
if(c1!=c2){
(distinct palidromic subsequence)
dps(c1mc2)=dps(c1m)+dps(mc2)-dps(m);
//get understanding through set theory s2,s3,s1 and through above formula find distinct palidromic non-empty subsequence (union) 
i->intersection
=s1+s2+s3-(s1is2)-(s1is3)-(s2is3)+(s1is2is3)
since in set c1m and set mc2 there is nothing common so
=s1+s2+s3-(s1is2)-(s1is3)-0+0 +s1-s1
(s1+s2-(s1is2))+(s1+s3-(s1is3))-s1
which gives above formula

}else if( c1==c2){
if(mid string doesn't have c1)

=s1+s2+s3+s4-(s1is2)-(s1is3)-(s1is4)-(s2is3)-(s2is4)-(s3is4)+(s1is2is3)+(s2is3is4)+(s1is3is4)+(s1is2is4)-(s1is2is3is4)
dps(c1mc2)=2dps(m)+2 proved through set theory, it will cover all 4{(c1m),(m),(mc2),(c1mc2)} cases and then come to some conclusion

}else if( mid string have 1 c1){

dps(c1mc2)=2dps(m)+1
just make sets all 4 sets just like above and then after analyzing you will found that only s1(m)and s4(c1mc2) will be left as we know that s4 contains s1+1 subsequence (extra 1 because empty string become valid)

}else if( mid string have more than 1 c1){
dps(c1mc2)=2*dps(m)-dps(m')
}
###And in this question also we are representing row as starting character, and column as ending character

 public int CountDifferentPalindromicSubsequences(String str){
        int dp[][]=new int[str.length()][str.length()];
        
        int[]prev=new int[str.length()]; //this will give me indx of prev (same)character if any
        HashMap<Character,Integer>map=new HashMap<>();
        for(int i=0;i<prev.length;i++){
            if(!map.containsKey(str.charAt(i))){
                prev[i]=-1;
            }else{
                prev[i]=map.get(str.charAt(i));
            }
            map.put(str.charAt(i),i);
        }
        
        map.clear();
        int[]next=new int[str.length()];
        
        for(int i=next.length-1;i>=0;i--){
            if(!map.containsKey(str.charAt(i))){
                next[i]=-1;
            }else{
                next[i]=map.get(str.charAt(i));
            }
            map.put(str.charAt(i),i);
        }
               
        
        for(int gap=0;gap<str.length();gap++){
            for(int i=0,j=gap;j<str.length();i++,j++){
                if(gap==0){
                    dp[i][j]=1;
                }else if(gap==1){  //2 characters
                    dp[i][j]=2;
                }else{
                    if(str.charAt(i)!=str.charAt(j)){
                        dp[i][j]=((dp[i+1][j]+dp[i][j-1])%m-dp[i+1][j-1])%m;
                    }else{
                        int n=next[i];
                        int p=prev[j];
                        if(n>p){ //0 same character in mid
                            dp[i][j]=(2*dp[i+1][j-1]%m+2)%m;
                        }else if(n==p){ //1 same character
                            dp[i][j]=(2*dp[i+1][j-1]%m+1)%m;
                        }else{     // more than 1 same character
                            dp[i][j]=(2*dp[i+1][j-1]%m-dp[n+1][p-1])%m;
                        }
                    }
                }
                if (dp[i][j] < 0) dp[i][j] = (dp[i][j] + m )%m;
            }
        }
        
       return dp[0][str.length()-1];     
    }



------------------------------------------------------------------------------------------------
26. Longest Palindromic Subsequence
-> Method1) Find LCS of (str,reverse of str).

Method 2)->

*) str= c1+m+c2 
->sq(str)= c1(yes/no)+ sq(m) + c2(yes/no)
->sq(c1 m)=c1(yes/no) +sq(m)
->sq(m c2)=sq(m)+c2(yes/no)
->sq(m)=sq(m) 

s1->m , s2-> c1m , s3-> mc2 , s4-> c1mc2

now if(c1!=c2){  //ans can't lie in set4 
-> max(lps(s1),lps(s2),lps(s3))
but lps(s2) represents ->(s1,s2), and similarly lps(s3) represents (s1,s3)
so ans=Max(lps(s2),lps(s3))
}else{ //ans only lies in set 4
lps=lps(mid)+2
}

 public int longestPalindromeSubseq(String s) {
        int[][]dp=new int[s.length()][s.length()];
        
        for(int gap=0;gap<s.length();gap++){
            for(int i=0,j=gap;j<s.length();i++,j++){
                
                char c1=s.charAt(i);
                char c2=s.charAt(j);
                
                if(gap==0){
                    dp[i][j]=1;
                }else if(gap==1){
                    dp[i][j]=(c1==c2)?2:1;
                }else{
                    if(c1==c2){
                        dp[i][j]=dp[i+1][j-1]+2;
                    }else{
                        dp[i][j]=Math.max(dp[i][j-1],dp[i+1][j]);
                    }
                }
            } 
        }
     return dp[0][s.length()-1];   
    } 
------------------------------------------------------------------------------------------------
27.  Longest Palindromic Substring
->Use Count palidromic substring code, and just take a max variable, when you encounter with true value just check the length of string.
------------------------------------------------------------------------------------------------
28. Longest Alternating Subsequence
 public int AlternatingaMaxLength(int[] arr)
    {
       		int c = 0;
		for (int i = 0; i < arr.length - 1; i++) {
			if (arr[i] < arr[i + 1]) {
				c = 1;
				break;
			} else if (arr[i] > arr[i + 1]) {
				c = 2;
				break;
			}
		}
		if (c == 0) {
			return 1;
		}
		int[] dp = new int[arr.length + 1];
		Arrays.fill(dp, -1);
		boolean flag = (c == 1) ? true : false;
		return LongestAlternatingSubsequence(arr, 0, dp, flag);
    }
    int LongestAlternatingSubsequence(int[] arr, int idx, int[] dp, boolean f) {
		if (idx + 1 == arr.length)
			return 1;

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

		int u = 0, d = 0, p = 0;
		if (arr[idx] < arr[idx + 1] && f) {
			u = 1 + LongestAlternatingSubsequence(arr, idx + 1, dp, false);
		} else if (arr[idx] > arr[idx + 1] && !f) {
			d = 1 + LongestAlternatingSubsequence(arr, idx + 1, dp, true);
		}
		p = LongestAlternatingSubsequence(arr, idx + 1, dp, f);
		int ans = Math.max(u, Math.max(d, p));
		dp[idx] = ans;
		return ans;
	}
------------------------------------------------------------------------------------------------
29. GoldMine Problem
static int maxGold(int n, int m, int arr[][])
    {
        int j = 0;
		int max = 0;
		int[][] dp = new int[n + 1][m + 1];
		for (int r = 0; r < n; r++) {
			for (int c = 0; c < m; c++) {
				dp[r][c] = -1;
			}
		}
		for (int i = 0; i < arr.length; i++) {
			max = Math.max(max, GoldMineProblem(arr, n - 1, m - 1, i, j, dp));
		}
		return max;
    }
    public static int GoldMineProblem(int[][] arr, int row, int col, int i, int j, int[][] dp) {

		if (i > row || j > col || i < 0)
			return 0;
		if (dp[i][j] != -1)
			return dp[i][j];

		if (j == col)
			return arr[i][j];

		int dur = GoldMineProblem(arr, row, col, i - 1, j + 1, dp) + arr[i][j];// diagonally up towards right
		int r = GoldMineProblem(arr, row, col, i, j + 1, dp) + arr[i][j]; // right
		int ddr = GoldMineProblem(arr, row, col, i + 1, j + 1, dp) + arr[i][j];// diagonally down towards right

		int ans = Math.max(dur, Math.max(r, ddr));
		dp[i][j] = ans;
		return ans;
	}
------------------------------------------------------------------------------------------------
30. Maximum Sum increasing subsequence
->Used Longest Increasing subsequence problem
and just change { dp[i]=1+max; } To { dp[i]=nums[i]+max; }
------------------------------------------------------------------------------------------------
31. Count distinct subsequences
Logic-> "abcba"
we will take a HashMap<Character,Integer>map, in this character will have key as ( last occurence index)
so now  when 2nd time 'b' come then (i=3) dp[i]=2*dp[i-1]-dp[idx=just prev index of last occ of this character {here 0}] we did this because
   when 1st b come    when 2nd b come then also , below seq will be generated so we have to subtract that . 
.    b    			b
a   ab			ab 

public static int DistinctSubsequences(String s) {
		HashMap<Character,Integer>map=new HashMap<Character, Integer>();
		long[]dp=new long[s.length()+1];
		dp[0]=1; //empty seq
		for(int i=1;i< dp.length;i++) {
			
            			dp[i]=2*dp[i-1]%MOD;
			char ch=s.charAt(i-1);
            
			if(map.containsKey(ch)) {
				int j=map.get(ch);
				dp[i]=(dp[i]-dp[j-1])%MOD;
			}
            
            			map.put(ch,i);
		}

       		 if(dp[s.length()]<0){
           		 dp[s.length()]=(dp[s.length()]+MOD)%MOD;
      		  }
		return (int) (dp[s.length()]-1);// because we only need non-empyt seq
	}
------------------------------------------------------------------------------------------------
32. Egg Dropping Problem 
Keypoints:
*Optimize the badluck /for gurantee there are 2 options which are below
(do best when it is in your control)&(Assume worst will happen which is not in your control)
-Guaranteed best time-> Best of the worst
-Lucky Best time-> Best of the Best
#Intuition
Best choice of the worst Luck (min of the maxes) 
-> At each floor it is the luck that an egg survives or breaks, at each floor we will take the worst means maxofTwo(survive,break), and take overall min

At kth floor	
	survives	
e/f-------.------------> e/f-k
                .  Breaks
                .	----------->e-1/k-1

Base Case: e=0 , not possible
	f=0, 0 moves
	e=1, f moves
	f=1, 1 move
M1)
 public int EggDroppingPuzzle(int k,int n ){
        int[][]dp=new int[k+1][n+1];
        //k eggs,n floors
        
        for(int i=1;i<=k;i++){
            for(int j=1;j<=n;j++){
                if(i==1){
                    dp[i][j]=j;
                }else if(j==1){
                    dp[i][j]=1;
                }else{
                    int min=Integer.MAX_VALUE;
                    //mj=my j, pj= previous j
                    for(int mj=j-1,pj=0;mj>=0;mj--,pj++){
                        int a=dp[i][mj]; //egg survives
                        int b=dp[i-1][pj]; //egg breaks
                        int val=Math.max(a,b);
                        min=Math.min(val,min);
                    }
                    dp[i][j]=min+1;
                }
            }
        }
        return dp[k][n];
    }
M2) Binary Search->
		
------------------------------------------------------------------------------------------------
33. Optimal Strategy for a game
 public static long OptimalStrategyForAGame(int[]arr,int n){
        long dp[][]=new long[n][n];
        
        for(int gap=0;gap<n;gap++){
            for(int i=0,j=gap;j<n;i++,j++){
                if(gap==0){
                    dp[i][j]=arr[i];
                }else if(gap==1){
                    dp[i][j]=Math.max(arr[i],arr[j]);
                }else{
                    //first choice is ours, other choices are of luck
                    // choices of i,j after taking first i / j
                    // i-> (i+1)->{(i+1,j-1),(i+2,j)}
                    long val1=arr[i]+Math.min(dp[i+1][j-1],dp[i+2][j]);
                    //j-> (j-1)->{(i+1,j-1),(i,j-2)};
                    long val2=arr[j]+Math.min(dp[i+1][j-1],dp[i][j-2]);
                    dp[i][j]=Math.max(val1,val2);
                }
            }
        }
        return dp[0][n-1];
    }
------------------------------------------------------------------------------------------------
34. Max Sum of Rectangle No larger Than K (Leetcode 363)  //try to understand this using dry run
Same below Question but use this->
private int maxSumSubArray(int[] a , int k){

    int max = Integer.MIN_VALUE;
    int preSum = 0;
    TreeSet<Integer> ts = new TreeSet();
    ts.add(0);

    for(int i=0;i<a.length;i++){
        preSum += a[i];
        Integer gap = ts.ceiling(preSum - k);
        if(gap != null) max = Math.max(max, preSum - gap);
        ts.add(preSum);
    }
    return max;
} 
instead of Kadane's algo
------------------------------------------------------------------------------------------------
35. Maximum sum rectangle in a 2D matrix
->
 public static int MaximumSumRectangle(int[][] mat, int row, int col) {
		int msr = Integer.MIN_VALUE;
	    int[] helper = new int[col];
		for (int s = 0; s < row; s++) {
		    Arrays.fill(helper,0);
			for (int r = s; r < row; r++) {
				for (int c = 0; c < col; c++) {
					helper[c] += mat[r][c];
				}
				msr = Math.max(msr, KadaneAlgo(helper, col));
			}
		}
		return msr;
	}
------------------------------------------------------------------------------------------------
36. Minimum No. of Jumps to reach end.
public static long MinJumps(int[] nums, int vidx, long[] dp) {
		if (vidx >= nums.length-1)
			return 0;

		if (dp[vidx] != -1) {
			return dp[vidx];
		}

		long jumps = Integer.MAX_VALUE;
		for (int val = vidx+1; val <= vidx+nums[vidx]; val++) {
          			  if(nums[vidx]!=0)
			jumps = Math.min(jumps, MinJumps(nums,val, dp));
		}
		jumps+=1;
		dp[vidx] = jumps;
		return jumps;
	}
------------------------------------------------------------------------------------------------
37. Word Break Problem
 public boolean WordBreak(String str,Set<String>set,int start,Boolean[]dp){
       if(start==str.length()){
           return true;
       }
        
        if(dp[start]!=null){
            return dp[start];
        }
        
        for(int end=start+1;end<=str.length();end++){
            if(set.contains(str.substring(start,end))){
                if(WordBreak(str,set,end,dp)){
                    dp[start]=true;
                    return true;
                }
            }
        }
        dp[start]=false;
        return dp[start];
    }
------------------------------------------------------------------------------------------------
38. Assembly line Scheduling ALgorithm ->https://www.youtube.com/watch?v=8I0kiyxfrM0

 public static int carAssembleTime(int a[][], int t[][],
                                       int e[], int x[]) {
        int n = a[0].length;
         
        // time taken to leave first station in line 1 
        int first = e[0] + a[0][0];
 
        // time taken to leave first station in line 2
        int second = e[1] + a[1][0];
          
        for (int i = 1; i < n; i++) {
            int up = Math.min(first + a[0][i],
                    second + t[1][i] + a[0][i]),
                    down = Math.min(second + a[1][i],
                            first + t[0][i] + a[1][i]);
            first = up;
            second = down;
        }
  
        first += x[0];
        second += x[1];
  
        return Math.min(first, second);
    }
------------------------------------------------------------------------------------------------
39. Paint fence 
Logic-> we fix the last two colors
this is for n=2
i) they can be same (k ways)
ii) they can be different (k*(k-1)) ways

for n>=3 
a) when last fence have same colors -> (all the ways of prev (n-1)th  (case ii) as they all are different and last color can be append to make this very case) 
b) total of previous (n-1)th  * (k-1) because every color can be append with k-1 colors leaving itself to make the last two colors different.

 long countWays(int n,int k)
    {
        if(n==0)
        return 0;
        if(n==1)
        return k;
           
        long same=(k*1)%mod;
        long diff=(k*(k-1))%mod;
        long total=(same+diff)%mod;
        
        for(int i=3;i<=n;i++){
            same=(diff*1)%mod;
            diff=(total*(k-1))%mod;
            total=(same +diff)%mod;
        }
        return total%mod;
    }
---------------------------->
long countWays(int n,int k)
    {
         if(n==0)
        return 0;
        if(n==1)
        return k;
        
       long dp[]=new long[n+1];
		dp[0] = 0;
		dp[1] = k;
		dp[2] = k * k;

		for (int i = 3; i <= n; i++) {
			dp[i] = ((k - 1) * (dp[i - 1] + dp[i - 2])) % mod;
		}
		return dp[n];
                       }
------------------------------------------------------------------------------------------------
40. Maximize the cut Segments
public int maximizeCuts(int n, int x, int y, int z)
    {
        int[]dp=new int[n+1];
        Arrays.fill(dp,-1);
       int ans=MaximizeCutsSegments(n,x,y,z,dp);
        if(ans<0)return 0;
        return ans;
        
    }
    public int MaximizeCutsSegments(int n,int x,int y,int z,int[]dp){
        if(n==0)
        return 0;
        
        if(n<0)
        return Integer.MIN_VALUE;
        
        if(dp[n]!=-1){
            return dp[n];
        }
        
        int a=MaximizeCutsSegments(n-x,x,y,z,dp)+1;
        int b=MaximizeCutsSegments(n-y,x,y,z,dp)+1;
        int c=MaximizeCutsSegments(n-z,x,y,z,dp)+1;
        
        return dp[n]=Math.max(a,Math.max(b,c));
        
    }
------------------------------------------------------------------------------------------------
41. Maximum size square sub-matrix with all 1s
Logic-> what is the max size of square that can be made if we set a point as top left point of square
 public int maximalSquare(char[][] matrix) {
		int m = matrix.length;
		int n = matrix[0].length;
		int[][] dp = new int[m][n];

		int ans = 0;
		for (int i = matrix.length - 1; i >= 0; i--) {
			for (int j = matrix[0].length - 1; j >= 0; j--) {
				if (matrix[i][j] == '0') {
					dp[i][j] = 0;
				} else {
					if (i == matrix.length - 1 || j == matrix[0].length - 1) {
						dp[i][j] = 1;
					} else {
						dp[i][j] = Math.min(dp[i + 1][j + 1], Math.min(dp[i + 1][j], dp[i][j + 1])) + 1;
					}
				}
				ans = Math.max(ans, dp[i][j]);
			}
		}
		return ans*ans;
	}
------------------------------------------------------------------------------------------------
42. Min / Max Path Sum In Matrix 
-> Same as gold mine problem
	public int MinPathSum(int[][] arr, int row, int col, int i, int j, int[][] dp) {
        		if(i==row&& j==col)
        		    return arr[i][j];
        
       		 if (i > row || j > col)
			return 10000;
        
      		  if (dp[i][j] != -1)
			return dp[i][j];

		int d = MinPathSum(arr, row, col, i + 1, j, dp) + arr[i][j];
		int r = MinPathSum(arr, row, col, i, j + 1, dp) + arr[i][j];
		
		int ans = Math.min(d,r);
		dp[i][j] = ans;
		return ans;
	}
------------------------------------------------------------------------------------------------
43.  Maximum difference of zeros and ones in binary string 
Logic-> convert "0"-> "1"  and  "1" -> "-1" and apply Kadane's algo
------------------------------------------------------------------------------------------------
44. Count number of ways to reacha given score in a game
-> Same as Coin change problem (combination)
------------------------------------------------------------------------------------------------
45. Minimum cost to fill given weight in a bag 
->Kind of Unbounded Knapsack
static long MinimumCost(int cost[], int N, int W, int i, long[][] dp) {
		if (W <= 0)
			return 0;
		if (i == N) {
			return 1000000000;  //check if this fxn return this value means not possible case
		}
		if (dp[i][W] != -1)
			return dp[i][W];

		if (cost[i] != -1 && W >= i + 1) {
			return dp[i][W] = Math.min(cost[i] + MinimumCost(cost, N, W - i - 1, i, dp),
					MinimumCost(cost, N, W, i + 1, dp));
		} else
			return dp[i][W] = MinimumCost(cost, N, W, i + 1, dp);
	}
------------------------------------------------------------------------------------------------
46. Maximum Profit in Job Scheduling
DP->
public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        int n = profit.length, res =0;
        int[][] mat = new int[n][3];
        int[] dp = new int[n];
        for(int i=0;i<n;i++){
            mat[i][0]=startTime[i];
            mat[i][1]=endTime[i];
            mat[i][2]=profit[i];
        }
        
        Arrays.sort(mat,(a,b)->a[0]-b[0]);
        
        for(int i=0;i<n;i++){
            int sum=mat[i][2];
            for(int j=0;j<i;j++)
                if( mat[j][1]<=mat[i][0] )
                    sum= Math.max( sum, dp[j]+mat[i][2] );            
            dp[i]=sum;
            res = Math.max(res,dp[i]);
        }
        return res;    
    }
DP+Binary Search->
 public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        int n = profit.length, res =0;
        int[][] mat = new int[n][3];
        int[] dp = new int[n];
        for(int i=0;i<n;i++){
            mat[i][0]=startTime[i];
            mat[i][1]=endTime[i];
            mat[i][2]=profit[i];
        }
        
        Arrays.sort(mat,(a,b)->{
		//If two jobs have same starting time, then choose job that ends before.
            if(a[0]==b[0]) return a[1]-b[1];
            return a[0]-b[0];
        });
        
        for(int i=n-1;i>=0;i--){
            int j = ceil(mat,mat[i][1],i+1,n-1);
			/*
			Choose best option between 
			1.Exclude current job and looking for max profit from next index OR
			2.Include current job and add max profit from the first interval that 
			doesnot overlap with current ending interval.
			*/
            dp[i] = Math.max( (i+1 <n ? dp[i+1] : 0) ,mat[i][2]+ ((j==-1)?0:dp[j]));
            res=Math.max(res,dp[i]);
        }
        
        return res;
    }
    
    private int ceil(int[][] mat, int val,int start, int end){
        if(start>end || val> mat[end][0]) return -1;
        if(start==end) return (val<=mat[start][0])?start:-1;
        int mid;
        while(start<=end){
            mid= start+ (end-start)/2;
            if(val==mat[mid][0]) return mid;
            else if(val>mat[mid][0]) start= mid+1;
            else end=mid-1;
        }
        return start;
    }
------------------------------------------------------------------------------------------------
47. Coin game winner where every player has three choices
static boolean findWinner(int x, int y, int n)
    {
        // To store results
        boolean[] dp = new boolean[n + 1];
      
        Arrays.fill(dp, false);
     
        // Initial values
        dp[0] = false;
        dp[1] = true;
      
        // Computing other values.
        for (int i = 2; i <= n; i++) {
      
            // If A losses any of i-1 or i-x
            // or i-y game then he will
            // definitely win game i
            if (i - 1 >= 0 && dp[i - 1] == false)  //false here denotes that last turn was of B
                dp[i] = true;
            else if (i - x >= 0 && dp[i - x] == false)
                dp[i] = true;
            else if (i - y >= 0 && dp[i - y] == false)
                dp[i] = true;
      
            // Else A loses game.
            else
                dp[i] = false;
        }
      
        // If dp[n] is true then A will
        // game otherwise  he losses
        return dp[n];
    }
------------------------------------------------------------------------------------------------
48.  Longest subsequence such that difference between adjacent is one
Logic-> Just like Longest Increasing Subsequence, we just need to check for difference of 1 instead checking whether current element
is strictly increasing than prev taken.
------------------------------------------------------------------------------------------------
49. Maximum Length of Pair Chain
public int findLongestChain(int[][] pair) {
     Chain[] arr=new Chain[pair.length];
        for(int i=0;i<pair.length;i++){
            int a=pair[i][0];
            int b=pair[i][1];
            arr[i]=new Chain(a,b);
        } 
     Arrays.sort(arr); //on the basis of first element
     return LIS(arr);  //on the basis of first element of curr should be greater than prev selected second.
    }
------------------------------------------------------------------------------------------------
50.Interleaving Strings
 public boolean InterleavingString(String s1,String s2,String s3,int i,int j,Boolean[][]dp){
        if(i==s1.length() && j==s2.length())
            return true;
        
        if(dp[i][j]!=null)
            return dp[i][j];
        
        
        boolean ans=false;
        if(i<s1.length() && j<s2.length() && s1.charAt(i)==s2.charAt(j) && s2.charAt(j)==s3.charAt(i+j)){
            boolean op1=InterleavingString(s1,s2,s3,i+1,j,dp);
            boolean op2=InterleavingString(s1,s2,s3,i,j+1,dp);
            ans=op1||op2;    
        }else if(i<s1.length() && s1.charAt(i)==s3.charAt(i+j)){
           ans=InterleavingString(s1,s2,s3,i+1,j,dp);
        }else if(j<s2.length() && s2.charAt(j)==s3.charAt(i+j)) {
            ans=InterleavingString(s1,s2,s3,i,j+1,dp);
        }
        dp[i][j]=ans;
        return ans;
    }
Bottom up-->
public boolean isInterleave(String s1, String s2, String s3) {
int len1 = s1.length();
int len2 = s2.length();
int len3 = s3.length();

    if(len1 + len2 != len3){
        return false;
    }
    
    boolean [][] dp = new boolean[len2+1][len1+1];
    // basic case
    dp[0][0] = true;
    
    //filling the first row in the 2D matrix boolean dp matrix by iterating j in column
    for(int j = 1; j < dp[0].length; j++){
        //left side value
        dp[0][j] = dp[0][j-1] && (s1.charAt(j-1)==s3.charAt(j-1));
    }
    //filling the first column in the 2D matrix boolean dp matrix by iterating i in row
    for(int i=1; i<dp.length; i++){
        dp[i][0] = dp[i-1][0] && (s2.charAt(i-1) == s3.charAt(i-1));
    }
    
    //
    for(int i=1; i<dp.length; i++){
        for(int j=1; j<dp[0].length; j++){
            dp[i][j] = dp[i-1][j] && (s2.charAt(i-1)==s3.charAt(i+j-1)) || dp[i][j-1] &&
                (s1.charAt(j-1)==s3.charAt(i+j-1));
        }
    }
    return dp[len2][len1];
}

Space optimised O(s2.length())

------------------------------------------------------------------------------------------------
51. Buy And Sell STocks I
Intuition-> Basically peak valley approach,but we can also understand with something that->
If we sell the stock on today then what is the max profit, for this we go to past in time machine and see when there is least price of the 
stock, we bought the stock at that day.

* Buy And Sell Stock II
->First traverse normal and check at every day the Max(if we sell the stock at this day what would be the 
max profit(Check above intuition), if we sell the stock till today what will be the max profit)

->Second traverse , reverse traverse and check at every day the Max of two cases.
Case1: if we have to buy the stock today (mandatory) then what would be the profit
(Basically we go to future in time machine and then check when the stock have max value, we will sell on that day)
Case2: if we have to buy the stock from today (including today, means henceforth) (form reverse)then the max profit

At last sum the both transactions (from both traversals) and find the max SUm.

 public int maxProfit(int[] prices) {
        int mpist=0;//max profit if sold today
        int leastsf=prices[0]; //least so far
        int[] dps=new int[prices.length]; //dp of max profit sold until today
        
        for(int i=1;i<prices.length;i++){
            if(leastsf>prices[i]){
                leastsf=prices[i];
             }
            
            mpist=prices[i]-leastsf;
            dps[i]=Math.max(dps[i-1],mpist);
        }
        
        int mpibt=0;//max profit if bought today
        int maxat=prices[prices.length-1];//max after today
        int[] dpb=new int[prices.length]; 
        //dp of max profit bought from today including curr day (henceforth)  
        for(int i=prices.length-2;i>=0;i--){
            if(maxat<prices[i]){
                maxat=prices[i];
            }
            
            mpibt=maxat-prices[i];
            dpb[i]=Math.max(mpibt,dpb[i+1]);
        }
        //now we sum both the  non-overlapping transaction best on right and best on left
        int op=0;
        for(int i=0;i<prices.length;i++){
            op=Math.max(op,dps[i]+dpb[i]);
        }
        return op;        
    }
------------------------------------------------------------------------------------------------
52. Buy And Sell Stocks (K transactions allowed)
Logic->
Here we put days on column and no transactions on rows. 
at a particular cell we define that on this day if we are allowed this much transaction then what would be the max profit
So, There are two cases
Case1: if we are on ith day and we are allowed t transactions and if (i-1)th day all t transaction are done. then it will contribute.
Case2: if (t-1)transactions have already happened on (0 to (i-1)th)day then profit from this will be max of all the days from 0 to (i-1)th
day and the transaction between current day and ith day.
= dp[ith(0 to (i-1)th )] + price[curr]-price[ith]; 
Ans At dp[i]=max of both the cases.

Done for Optimization
in case 2 we basically need max of all the transaction before curr day for t-1 transaction
dp[i]+price[curr]-price[i]; for all the i's we have price[curr] is common
so we need to maximize dp[i]-price[i]; ans at last add price[curr]

 public int maxProfitKtransactions(int k, int[] prices) {
        int n=prices.length;
        if(n==0)
        return 0;
        
        int[][]dp=new int[k+1][n];
    //for row=0 or col=0 ans is 0 
    //0 ans in 0th row means 0 transaction therefore no profit
    //0 ans in 0th col means single day so not selling so 0 profit    
        for(int t=1;t<=k;t++){
            int mx=Integer.MIN_VALUE;
            for(int d=1;d<n;d++){
                mx=Math.max(mx,dp[t-1][d-1]-prices[d-1]);
                dp[t][d]=Math.max(dp[t][d-1],mx+prices[d]);
            }   
        }
        return dp[k][n-1];
    }

------------------------------------------------------------------------------------------------
53. Mobile numeric keypad
Logic-> if we can press n keys then dp[i] stores that if n keys are pressed and if last key(nth key) pressed is "i" then
how many words are there (basically seq of numbers)
	public long getCount(int N)
	{
		long[]dp=new long[10];
		Arrays.fill(dp,1);
		int[][]data=new int[10][];
		data[0]=new int[]{0,8};
		data[1]=new int[]{1,2,4};
		data[2]=new int[]{2,1,3,5};
		data[3]=new int[]{3,2,6};
		data[4]=new int[]{4,1,5,7};
		data[5]=new int[]{5,2,4,6,8};
		data[6]=new int[]{6,3,9,5};
		data[7]=new int[]{7,8,4};
		data[8]=new int[]{8,5,7,9,0};
		data[9]=new int[]{9,6,8};
		
		for(int i=2;i<=N;i++){
		    long[]dpp=new long[10];
		    for(int j=0;j<=9;j++){
		        for(int k:data[j])
		            dpp[j]+=dp[k];
		    }
		    dp=dpp;
		}
		long ans=0;
		for(long val:dp)
		    ans+=val;
		  
		return ans;    
	}
------------------------------------------------------------------------------------------------
54. Maximum subsequence sum such that no three are consecutive
static int maxSumWO3Consec(int arr[], int n)
    {
        // Stores result for subarray arr[0..i], i.e.,
        // maximum possible sum in subarray arr[0..i]
        // such that no three elements are consecutive.
        int sum[] = new int[n];
 
        // Base cases (process first three elements)
        if (n >= 1)
            sum[0] = arr[0];
 
        if (n >= 2)
            sum[1] = arr[0] + arr[1];
 
        if (n > 2)
            sum[2] = Math.max(sum[1], Math.max(arr[1] + arr[2], arr[0] + arr[2]));
 
        // Process rest of the elements
        // We have three cases
        // 1) Exclude arr[i], i.e., sum[i] = sum[i-1]
        // 2) Exclude arr[i-1], i.e., sum[i] = sum[i-2] + arr[i]
        // 3) Exclude arr[i-2], i.e., sum[i-3] + arr[i] + arr[i-1]
        for (int i = 3; i < n; i++)
            sum[i] = Math.max(Math.max(sum[i - 1], sum[i - 2] + arr[i]),
                              arr[i] + arr[i - 1] + sum[i - 3]);
 
        return sum[n - 1];
    }
------------------------------------------------------------------------------------------------
55. Boolean Parenthesization 
->
 ltc/lfc       rtc/rfc    //ltc->left true count
 (lhs) operand (rhs)      //lfc-> left false count

Operands->
	    tc                        fc	
& ->   ltc*rtc                     ltc*rfc+lfc*rtc+lfc*rfc
| ->   ltc*rfc+lfc*rtc+ltc*rtc     lfc*rfc
^ ->   ltc*rfc+lfc*rtc  	   ltc*rtc+lfc*rfc

public int countParenth(char[] symb, char[] oper) {
        int n=symb.length;
        int[][]dpt=new int[n][n];
        int[][]dpf=new int[n][n];

        for(int gap=0;gap<n;gap++){
            for(int i=0,j=gap;j<n;j++,i++){
                if(gap==0){
                  if(symb[i]=='T'){
                      dpt[i][j]=1;
                      dpf[i][j]=0;
                  }else{
                      dpt[i][j]=0;
                      dpf[i][j]=1;
                  }
                }else{
                    for(int k=i;k<j;k++){
                        int ltc=dpt[i][k];
                        int rtc=dpt[k+1][j];
                        int lfc=dpf[i][k];
                        int rfc=dpf[k+1][j];
                        if(oper[k]=='&'){
                            dpt[i][j]+=ltc*rtc;
                            dpf[i][j]+=ltc*rfc+lfc*rtc+lfc*rfc;
                        }else if(oper[k]=='|'){
                            dpt[i][j]+=ltc*rfc+lfc*rtc+ltc*rtc;
                            dpf[i][j]+=lfc*rfc;
                        }else{
                            dpt[i][j]+=ltc*rfc+lfc*rtc;
                            dpf[i][j]+=ltc*rtc+lfc*rfc;
                        }
                    }
                }
            }
        }
          return dpt[0][n-1]; 
    }
------------------------------------------------------------------------------------------------
56. Optimal Binary Search Tree 
#Keypoints->
no. of comparisons= depth of the element in the tree

 private static void optimalbst(int[] keys, int[] freq, int n) {
    int[][]dp=new int[n][n];
    int[]psa=new int[n]; // so that we will not calculate sum of freq again n again
    // and we need this because by adding this req value, we are adding the current element in the bst
    // which increases the other's depth  by 1.
    //suppose ans of c-d  is 2  (min(c'+2d',d'+2c')=c'+2d') now if we want ans of
    // a-(c-d) then the ans will be c'+2d'+(a'+c'+d')
    
    psa[0]=freq[0];
    for(int i=1;i<psa.length;i++){
        psa[i]=psa[i-1]+freq[i];
    }
    
    for(int gap=0;gap<n;gap++){
        for(int i=0,j=gap;j<n;j++,i++){
            if(gap==0){
                dp[i][j]=freq[i];
            }else if(gap==1){
                int f1=freq[i];
                int f2=freq[j];
                dp[i][j]=Math.min(f1+2*f2,f2+2*f1);
            }else{
                int min=Integer.MAX_VALUE;
                int fr=psa[j]-((i==0)?0:psa[i-1]);
                for(int k=i;k<=j;k++){
                    int left=((k==i)?0:dp[i][k-1]);
                    int right=((k==j)?0:dp[k+1][j]);
                    min=Math.min(min,left+right+fr);
                }
                dp[i][j]=min;
            }      
        }
    }
      System.out.println(dp[0][n-1]);
    }
------------------------------------------------------------------------------------------------
57. Count Balanced Binary Trees of Height h
static long countBT(int h){
        if(h==0||h==1)
            return 1;
            
            long mod=1000000007;
            long[]dp=new long[h+1];
            dp[0]=dp[1]=1;
            
            // case1: c(h-1)*c(h-1);
            // case2: c(h-1)*c(h-2);
            // case3: c(h-2)*c(h-1);
            for(int i=2;i<=h;i++){
                dp[i]=( dp[i-1]*( (2*dp[i-2])%mod + dp[i-1]) )%mod;
            }
            return dp[h];
        }
------------------------------------------------------------------------------------------------
58. Minimum removals from array to make max –min <= K
Dp->
static int countRemovals(int a[], int i, int j, int k)
    {
        // base case when all elements are removed
        if (i >= j)
            return 0;
     
        // if condition is satisfied, no more
        // removals are required
        else if ((a[j] - a[i]) <= k)
            return 0;
     
        // if the state has already been visited
        else if (dp[i][j] != -1)
            return dp[i][j];
     
        // when Amax-Amin>d
        else if ((a[j] - a[i]) > k) {
     
            // minimum is taken of the removal
            // of minimum element or removal
            // of the maximum element
            dp[i][j] = 1 + Math.min(countRemovals(a, i + 1, j, k),
                                    countRemovals(a, i, j - 1, k));
        }
        return dp[i][j];
    }
Binary Search->

static int removals(int arr[], int n, int k)
{
    int i, j, ans = n - 1;
     
    // Sort the given array
    Arrays.sort(arr);
     
    // Iterate from 0 to n-1
    for(i = 0; i < n; i++)
    {
         
        // Find max(so that we have to remove lesser no of elements) value of j such that
        // arr[j] - arr[i] <= k 
        j = findInd(arr[i], i, n, k, arr);
         
        // If there exist such j
        // that satisfies the condition
        if (j != -1)
        {
             
            // Number of elements
            // to be removed for this
            // particular case is
            // (j - i + 1)
            ans = Math.min(ans,
                           n - (j - i + 1));
        }
    }
    return ans;
}

static int findInd(int key, int i,
                   int n, int k, int arr[])
{
    int start, end, mid, ind = -1;
    start = i + 1;
    end = n - 1;
     
    // Binary search implementation
    // to find the rightmost element
    // that satisfy the condition
    while (start < end)
    {
        mid = start + (end - start) / 2;
        if (arr[mid] - key <= k)
        {    
            ind = mid;
            start = mid + 1;
        }
        else
        {            
           end = mid;
        }
    }
     
    // Return the rightmost position
    return ind;
}

------------------------------------------------------------------------------------------------
59. Wine Problem
public static int WineProblemTD(int[] arr, int si, int ei, int[][] strg) {
		int year = arr.length - ei + si;
		if (si == ei) {
			return arr[si] * year;
		}
		if (strg[si][ei] != 0) {
			return strg[si][ei];
		}
		int first = WineProblemTD(arr, si + 1, ei, strg) + arr[si] * year;
		int last = WineProblemTD(arr, si, ei - 1, strg) + arr[ei] * year;

		int ans = Math.max(first, last);
		strg[si][ei] = ans;
		return ans;

	}

	public static int WineProblemBU(int[] arr) {
		int n = arr.length;
		int[][] strg = new int[n][n];
		for (int slide = 0; slide <= n - 1; slide++) {
			for (int si = 0; si <= n - slide - 1; si++) {
				int ei = si + slide;
				int year = arr.length - ei + si;
				if (si == ei) {

					strg[si][ei] = arr[si] * year;
					continue;
				}
				int first = strg[si + 1][ei] + arr[si] * year;
				int last = strg[si][ei - 1] + arr[ei] * year;

				int ans = Math.max(first, last);
				strg[si][ei] = ans;

			}
		}
		return strg[0][n - 1];
	}

------------------------------------------------------------------------------------------------
60. HarryPotter Color Mixture
public static int harrypottercolormixturesTD(int[] arr, int si, int ei, int[][] strg) {
		if (si == ei) {
			return 0;
		}

		if (strg[si][ei] != 0) {
			return strg[si][ei];
		}
		int ans = Integer.MAX_VALUE;
		for (int k = si; k <= ei - 1; k++) {
			int fp = harrypottercolormixturesTD(arr, si, k, strg);
			int sp = harrypottercolormixturesTD(arr, k + 1, ei, strg);
			int sw = resultingcolour(arr, si, k) * resultingcolour(arr, k + 1, ei);

			int overall = sw + fp + sp;
			if (overall < ans) {
				ans = overall;
			}
		}
		strg[si][ei] = ans;
		return ans;
	}

	public static int resultingcolour(int[] arr, int i, int j) {
		int sum = 0;
		for (int k = i; k <= j; k++) {
			sum += arr[k];
		}
		return sum % 100;
	}

	public static int harrypottercolormixturesBU(int[] arr) {
		int n = arr.length;
		int[][] strg = new int[n][n];

		for (int slide = 1; slide <= n - 1; slide++) {
			for (int si = 0; si <= n - slide - 1; si++) {
				int ei = si + slide;
				int ans = Integer.MAX_VALUE;
				for (int k = si; k <= ei - 1; k++) {
					int fp = strg[si][k];
					int sp = strg[k + 1][ei];
					int sw = resultingcolour(arr, si, k) * resultingcolour(arr, k + 1, ei);

					int overall = sw + fp + sp;
					if (overall < ans) {
						ans = overall;
					}
				}
				strg[si][ei] = ans;
			}
		}
		return strg[0][n - 1];
	}
----------------------------------------------------------------------------------
61. Rod Cutting
	public static int RodcuttingTD(int[] arr, int len, int[] strg) {

		if (strg[len] != 0) {
			return strg[len];
		}
		int profit = arr[len];
		int left = 1;
		int right = len - 1;
		while (left <= right) {
			int fp = RodcuttingTD(arr, left, strg);
			int sp = RodcuttingTD(arr, right, strg);

			int ans = fp + sp;
			profit = (profit < ans) ? ans : profit;
			left++;
			right--;
		}
		strg[len] = profit;
		return profit;

	}

	public static int RodcuttingBU(int[] arr) {
		int[] strg = new int[arr.length];
		for (int i = 1; i < strg.length; i++) {
			int profit = arr[i];
			int left = 1;
			int right = i - 1;
			while (left <= right) {
				int fp = strg[left];
				int sp = strg[right];

				int ans = fp + sp;
				profit = (profit < ans) ? ans : profit;
				left++;
				right--;
			}
			strg[i] = profit;
		}
		return strg[arr.length - 1];

	}

------------------------------------------------------------------------------------------------

------------------------------------------------------------------------------------------------

------------------------------------------------------------------------------------------------

------------------------------------------------------------------------------------------------

------------------------------------------------------------------------------------------------

------------------------------------------------------------------------------------------------

------------------------------------------------------------------------------------------------

------------------------------------------------------------------------------------------------

------------------------------------------------------------------------------------------------

------------------------------------------------------------------------------------------------

------------------------------------------------------------------------------------------------

------------------------------------------------------------------------------------------------