Dynamic Programming.txt

Important Concetps

-> All DP problems according to its type -> https://leetcode.com/discuss/study-guide/1000929/Solved-all-dynamic-programming-(dp)-problems-in-7-months

1) Whenever there will be relation like dp[i-1], dp[i-2] there can always be space optimization like
curr = accoding to question
prev2=prev;
prev=curr;
-> If there is a prev row & prev column, we can space optimise it.

-> in place of dp[i-1][j] we can write prev[j]  and in place of dp[i][j-1] we can write curr[j-1].

& if there is array concept in space optimization then make it front array and next array and after work just set front array = next array

2) If there is any problem related to subsets for eg)
-> Count partitions with given difference s1-s2=d => total =s1+s2 => s2 = (total-d)/2;
-> Count subsets with sum k
-> Partition Equal subset sum => make total sum then find subset having sum total/2
-> Partition A set into two subsets with minimum Abs sum differece -> Q13) in Backtracking file
=> These all problems boils down to same. just by modifying the target.

3) In Partition type Dp
-> we see that we get different answers on different pattern pattern (like by different way, we get diff ans).
-> Here we take whole block of array and solve for every possible partition and calculate ans accordingly.

Rules:
-> In top down suppose we call for solve(1,n-1)<=>solve(i,j)
-> In bottom up since we write just opposite. but here is something to think about.
-> IN CASE OF PARTITION DP
-> for(int i=n-1;i>=1;i++) and for the jth loop it doesn't start 0 instead i or i+1
-> for(int j=i+1;j<n;j++) because i can't be greater than j to get valid set of blocks of array.

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];
    }

-> Extreme Space Optimised with just 1D array (Striver's solution)

// here below we can't move w from 0 to capacity because if we do so then the prev values of dp array will be 
override and as we know that for each w we are dependent on prev values of dp to compute the current ans.

public int solve(int[] weights, int[] values, int capacity) {
        int n = values.length;
        int[]dp = new int[capacity+1];

        for(int idx = 0; idx<n; idx++){
            for(int w = capacity; w>=0; w--){
                int notTake = dp[w];
                int take = Integer.MIN_VALUE;
                if(w>=weights[idx]){
                    take = values[idx] + dp[w-weights[idx]]; 
                }
                dp[w]=Math.max(take,notTake);
            }
        }
        return dp[capacity];
    }
----------------- -------------------------------------------------------------------------------
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;
	}

#) Minimum Insertions/Deletions to Convert String A to String B
 -> Keep the equal portion intact.

Eg) abcd , anc
abcd -> 2 deletions + ac -> 1 insertions makes anc

 -> Deletions = len(a)-lcs(a,b);
 -> Insertions = len(b)-lcs(a,b);

 -> ans = (len(a)+len(b) - 2 * LCS(A,B)); 	
------------------------------------------------------------------------------------------------
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];
	}

#) Printing LCS
-> after tabulation,get the 2d dp array.
int len = dp[n][m];
String ans = "";
for(int i=0;i<len;i++){
     ans+="$";	
}

O(m+n)

int idx = len-1;
int i=n, j=m;
while(i>0 && j>0){
    if(s[i-1]==t[j-1]){
	ans[idx]=s[i-1];
	idx--;
	i--,j--;	
   }else if(dp[i-1][j]>dp[i][j-1]{
	   i--;
   }else{
       j--;		
   }
 }
 System.out.println(ans);

------------------------------------------------------------------------------------------------
6. Palindromic Partitions/cuts 
-> Time Complexity (N^3) -> (N^2)
->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)

// we are cutting prefixes here (Front partition)

-> We can create another dp table in which dp[I][j] will tell whether substring s(I,j) is palindrome or not hence check function's time complexity reduces to O(1) and overall time complexity to O(n^2)


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) -> Leetcode:377 (Combination Sum IV) 
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=1;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;
	}

Striver's way ->

 public boolean canPartition(int[] nums) {
        int sum=0;
        for(int num:nums){
            sum+=num;
        }
        
        if(sum%2!=0)return false;
        
        int n = nums.length;
        
        int[][]dp = new int[n+1][sum/2 +1];
        
        for(int[]dpp:dp){
            Arrays.fill(dpp,-1);
        }
        int tar = sum/2;
        return partitionEqualSubsetSum(n-1,tar,nums,dp);
    }
    
    public boolean partitionEqualSubsetSum(int idx, int tar,int[]nums,int[][]dp){
        if(tar==0)return true;
        
        if(idx==0)return (nums[0]==tar);
    
        if(dp[idx][tar]!=-1){
            return (dp[idx][tar]==1)?true:false;
        }
        
        boolean pick = false;
        if(tar>=nums[idx]){
            pick = partitionEqualSubsetSum(idx-1,tar-nums[idx],nums,dp);    
        }
        
        boolean notPick = partitionEqualSubsetSum(idx-1,tar,nums,dp);

        boolean ans = pick || notPick;
        
        dp[idx][tar] = ((ans)? 1:2);
        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;
		//if i wants to be single then dp[i-1] will be called to find out in how many ways i-1 can be single or paired up
		// if i wants to pair up then it can be paired up with i-1 leaving itself, now if it get paired up then 
		//remaining members will be i-2 they can be single or paired up (through dp[i-2]) <- it will give ans for those, since this call will be 
		//called i-1 times therefore we multiplied this.
		}
		
		return dp[n];
	}
------------------------------------------------------------------------------------------------
14. Binomial Coefficient Problem (nCr)
Formula Used->   C(n, r) = C(n-1, r) + C(n-1, r-1) 
 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, r) = P(n-1, r) + r*P(n-1, r-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[]hash=new int[n]; // it will store the prev index of LIS
        Arrays.fill(dp,1);

        int omax=0;
        int lastmaxind = 0;
        
        for(int i=0;i<n;i++){
            int max=0;
            hash[i]=i;
            for(int j=0;j<i;j++){
                if(nums[i]>nums[j]){
                    if(dp[j]>max){
                        max=dp[j];
                        hash[i]=j;
                    }
                }
            }
            dp[i]=1+max;
            if(dp[i]>omax){
                omax=dp[i];
                lastmaxind=i;
            }
        }

// in order to print the LIS

	ArrayList<Integer>lis = new ArrayList<>();
	lis.add(nums[lastmaxind]);

        while(hash[lastmaxind]!=lastmaxind){
        	lastmaxind = hash[lastmaxind];
        	lis.add(nums[lastmaxind]);
        }

        Collections.reverse(lis);

        return omax;        
    }

->  Print no of LIS
 public int findNumberOfLIS(int[] nums) {
        int n = nums.length;

        int[]dp = new int[n];
        int[]cnt = new int[n];
        Arrays.fill(dp,1);
        Arrays.fill(cnt,1);

        int max = 0;

        for(int i=0;i<n;i++){
            for(int j=0;j<i;j++){
                if(nums[i]>nums[j]){
                    if(dp[i]<dp[j]+1){
                        dp[i]=dp[j]+1;
                        cnt[i]=cnt[j];
                    }else if(dp[i]==dp[j]+1){
                        cnt[i]+=cnt[j];
                    }
                }
            }
            max = Math.max(dp[i],max);
        }
        
        int count=0;
        for(int i=0;i<n;i++){
            if(dp[i]==max){
                count+=cnt[i];
            }
        }
        return count;
    }    

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 int lengthOfLIS(int[] nums) {
        int n = nums.length;
        
        int[]lis = new int[n+1];
        
        Arrays.fill(lis,Integer.MAX_VALUE);
        lis[0] = Integer.MIN_VALUE;
        
        
        int ans=0;
        for(int i=0;i<n;i++){
            int val = nums[i];
            int idx = lowerBound(lis,nums[i]);
            ans = Math.max(idx,ans);
            if(lis[idx]>=val){
                lis[idx]=val;
            }
        }
        
        return ans;
    }
     public int lowerBound(int[]dp, int val){
        int l=0, h=dp.length-1;
        int res = 0;
        
        while(l<=h){
            int mid = (l+h)>>1;
            if(dp[mid]<val){
                res=mid;
                l=mid+1;
            }else{
                h=mid-1;
            }
        }
        return res+1;
    }
-> Striver's Approach

  public int lengthOfLIS(int[] nums) {

		ArrayList<Integer> temp = new ArrayList<>();

		temp.add(nums[0]);
		int len = 1;

		for (int i = 1; i < nums.length; i++) {
			if (nums[i] > temp.get(temp.size() - 1)) {
				len++;
				temp.add(nums[i]);
			} else {
				int[] arr = temp.stream().mapToInt(id -> id).toArray();
				int idx = LowerBound(arr, 0, temp.size(), nums[i]);
				temp.set(idx, nums[i]);
			}
		}

		return len; // or temp.size();
	}
------------------------------------------------------------------------------------------------
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 / Maximum Length of Repeated Subarray (LeetCode 718)
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

pqabcxy <-compare all prefixes of both and find longest common suffix-> xyzabcp
# At point when we compare pqabc with xyzabc thats where we get our longest common suffix hence longest common substring.
-> abc here is suffix of these above prefixes in both <- 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];  //next of start
                        int p=prev[j];  //prev of end
                        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  //extra 2 for ending characters
}

 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
->
M1) Use Count palidromic substring code, and just take a max variable, when you encounter with true value just check the length of string.

M2) Use axis and orbit method.

M3) 

public String longestPalindrome(String s) {
        int start = 0;
        int end = 0;
        for (int i = 0; i < s.length(); i++) {
            //StringBuffer sb = new StringBuffer();
            //sb.append(s.charAt[i]);
            char c = s.charAt(i);
            int left = i;
            int right = i;

            //to skip the duplicates
            while (left >= 0 && s.charAt(left) == c) {
                left--;
            }

            //to skip the duplicates
            while (right < s.length() && s.charAt(right) == c) {
                right++;
            }

            while (left >= 0 && right < s.length()) {
                if (s.charAt(left) != s.charAt(right)) {
                    break;
                }
                left--;
                right++;
            }


           // left + 1 and right - 1 are actually the start and end index of the Palindromic string
            // we don't set "right" because String.substring function required end index exclusively
            left = left + 1;
            if (end - start < right - left) {
                start = left;
                end = right;
            }
        }

        return s.substring(start, end);
    }
------------------------------------------------------------------------------------------------
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;
	}
#) Very Similar problem
-> Wiggle Subsequence (LC-376)	
-> A wiggle sequence is a sequence where the differences between successive numbers strictly alternate between positive and negative. 
------------------------------------------------------------------------------------------------
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 by which b and ab 							    occurs two times due to prev index of last occurrence of b {. a} 
.    b    			. b  (no)   (yes) b   bb
a   ab			        a ab             ab   abb

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->
Time Complexity: O((n * k) * logn )
Space Complexity: O(n * k)

 public int superEggDrop(int k, int n) {
        int[][]dp=new int[k+1][n+1];
        
        for(int[]arr:dp){
            Arrays.fill(arr,-1);
        }
        
        return eggdrop(k,n,dp);
    }
    public int eggdrop(int eggs,int floors,int[][]dp){
        if(eggs==1||floors==1){
            return floors;
        }
        
        if(floors<=0){
            return 0;
        }
        if(dp[eggs][floors]>0)return dp[eggs][floors];
        
        int min=100000;
        int l=1;
        int h=floors;
        
        while(l<=h){
            int mid = (l+h)/2;
            int left = eggdrop(eggs-1,mid-1,dp);
            int right = eggdrop(eggs,floors-mid,dp);
            int temp = 1 + Math.max(left,right);
            if(left<right){  // since right is more than left and we need more in worst case 
                l = mid+1;   // so l=mid+1 to gain more temp for worst case : upward
            }else{
                h = mid-1;
            }
            min = Math.min(min,temp);
        }
        return dp[eggs][floors]=min;
    }
M3) Different approach
-> https://leetcode.com/problems/super-egg-drop/discuss/158974/C%2B%2BJavaPython-2D-and-1D-DP-O(KlogN)

# Below explanation is given by
->https://leetcode.com/Sandermatt/

-> He has turned the problem around from
"How many moves do you need to check N floors if you have K eggs"
to:
"How many floors can you check given M moves available and K eggs".

If you can solve this second problem than you can just increase the moves M one by one until you are able to check a number of floors larger or equal to the number N which the problem requires.
He then defined
dp[M][K] as the maximum number of floors that you can check within M moves given K eggs

A move essentially is dropping an egg and it either breaks or doesn't break.
Case A: The egg breaks and now you have spent 1 move (M=M-1) and also lost 1 egg (K=K-1). You can still check dp[M-1][K-1] floors, with your remaining eggs and moves.
Case B: The egg remains and you only loose one move (M=M-1). You can still check dp[M-1][K] floors.
Additionally you just checked a floor by dropping the egg from it.
Therefore dp[M][K] = dp[M - 1][k - 1] + dp[M - 1][K] + 1
As you can see we can easily calculate how many floors we can check in M moves if we know how many floors we can check in M-1 moves.

However we not only have to know how many floors we can can check with one move less, but also how many we can check with one move and one egg less. Therefore we have to calculate how many moves we can check for all number off eggs from 1 to K.

public int superEggDrop(int K, int N) {
       int[][] dp = new int[N + 1][K + 1];
        int m = 0;
        while (dp[m][K] < N) {
            ++m;
            for (int k = 1; k <= K; ++k)
                dp[m][k] = dp[m - 1][k - 1] + dp[m - 1][k] + 1;
        }
        return m;
    }		
------------------------------------------------------------------------------------------------
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->

-> below there we are finding ceiling value of (presum-k) / (can also find (presum-k)<- as sum can be equal to k
-> but treeset doesn't have get function ) because that will be the value which can be deleted to make sure that the sum is less than k.
Presum=k+x <- this x should be deleted from presum so that we get atleast k.

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;
	}

-> Similar question
(Count Squares submatrices with all ones - (LC-1277))
->	 public int countSquares(int[][] matrix) {
        int m = matrix.length;
		int n = matrix[0].length;
		int[][] dp = new int[m][n];

		
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(matrix[i][j]==0){
                    dp[i][j] = 0;
                }else{
                    if(i==0 || j==0){
                        dp[i][j]=1;
                    }else{
                        dp[i][j] = 1 + Math.min(dp[i-1][j],Math.min(dp[i-1][j-1],dp[i][j-1]));
                    }
                }
            }
        }
        
        int sum = 0;
        
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                sum+=dp[i][j];
            }
        }
        return sum;
    }

------------------------------------------------------------------------------------------------
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->

 -> Create a Job array for ease of calculation.
-> Sort jobs according to finish time.
-> For the job array jobs
maxprofit(int[] jobs, n){
a) if (n == 1) return jobs[0];
b) Return the maximum of following two profits.
-> Maximum profit by excluding current job : maxprofit(jobs, n-1)
-> Maximum profit by including the current job
}

Find Profit including current Job:
Find the latest job before the current job (in sorted array) that doesn't conflict with current job 'jobs[n-1]'.
Once found, we recur for all jobs till that job and add profit of current job to result.

Complexity : O(n Log n)

->
public class JobScheduling {

    private class Job {
        int start, finish, profit;
        Job(int start, int finish, int profit) {
            this.start = start;
            this.finish = finish;
            this.profit = profit;
        }
    }

    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        int n = startTime.length;
        Job[] jobs = new Job[n];
        for(int i=0;i<n;i++) {
            jobs[i] = new Job(startTime[i],endTime[i],profit[i]);
        }
        return scheduleApt(jobs);
    }

    private int scheduleApt(Job[] jobs) {
        // Sort jobs according to finish time
        Arrays.sort(jobs, Comparator.comparingInt(a -> a.finish));
        // dp[i] stores the profit for jobs till jobs[i]
        // (including jobs[i])
        int n = jobs.length;
        int[] dp = new int[n];
        dp[0] = jobs[0].profit;
        for (int i=1; i<n; i++) {
            // Profit including the current job
            int profit = jobs[i].profit;
            int l = search(jobs, i);
            if (l != -1)
                profit += dp[l];
            // Store maximum of including and excluding
            dp[i] = Math.max(profit, dp[i-1]);
        }

        return dp[n-1];
    }

    private int search(Job[] jobs, int index) {
        int start = 0, end = index - 1;
        while (start <= end) {
            int mid = (start + end) / 2;
            if (jobs[mid].finish <= jobs[index].start) {
                if (jobs[mid + 1].finish <= jobs[index].start)
                    start = mid + 1;
                else
                    return mid;
            }
            else
                end = mid - 1;
        }
        return -1;
    }

}
#) Very Similar Problem but solved using Heap only.
-> Two Best Non-Overlapping Events (Leetcode 2054)

->{startTime,endTime,Value}
-> Sort with respect to start time, and for the heap sort with respect to end time. so that we get the min end time
in logN time.

 public int maxTwoEvents(int[][] events) {
     int n = events.length;
        
     Arrays.sort(events, (a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);   
     PriorityQueue<int[]>pq = new PriorityQueue<>((a,b)->a[1]-b[1]);
     
     int max = 0;
     int res = 0;
     for(int i=0; i<n; i++){
         int start = events[i][0];
       
         while(!pq.isEmpty() && pq.peek()[1] < start){
             int[]arr = pq.poll();
             max = Math.max(max,arr[2]);
         }
         res = Math.max(res,events[i][2]+max);
         pq.add(events[i]);
     }                                             
        return res;
    }
------------------------------------------------------------------------------------------------
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;        
    }

 -> Recursively
 public int maxProfit(int[] prices) {
        return BuyNSellStockAtMost2(0,2,prices,0, new Integer[prices.length][2][3]);
        
    }
    public int BuyNSellStockAtMost2(int idx,int cap, int[]prices,int own,Integer[][][]dp){
        if(cap==0)return 0;
        
        if(idx==prices.length)return 0;
        
        if(dp[idx][own][cap]!=null){
            return dp[idx][own][cap];
        }
        
        if(own==1){
            int op1 = prices[idx]+BuyNSellStockAtMost2(idx+1,cap-1,prices,0,dp); //sell
            int op2 = BuyNSellStockAtMost2(idx+1,cap,prices,1,dp); //not sell
            return dp[idx][own][cap]=Math.max(op1,op2);
        }else{
            int op1 = -(prices[idx])+BuyNSellStockAtMost2(idx+1,cap,prices,1,dp); //buy
            int op2 = BuyNSellStockAtMost2(idx+1,cap,prices,0,dp); //not buy
            return dp[idx][own][cap]=Math.max(op1,op2);
        }
    }   
------------------------------------------------------------------------------------------------
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 upto 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 any of the(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 choosen ith day.from(0 to (i-1)th).
= 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];
    }
-> Recursively 
In above code just put k as capacity.
------------------------------------------------------------------------------------------------
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]; 
    }
-> Striver's method

static int mod = 1000000007;
    public static int evaluateExp(String exp) {
		int n = exp.length();
		long[][][]dp = new long[n][n][2];
		for(long[][]dpp:dp){
			for(long[]dppp:dpp){
				Arrays.fill(dppp,-1);
			}
		}
		int isTrue = 1; 
		// basically it represents what is required and since finally we required true 
 		// so we are passing that only.
        return (int)booleanEvaluation(0,n-1,isTrue,exp.toCharArray(),dp);
    }
	
	// here we are applying cuts on operator that's why idx+=2;
	public static long booleanEvaluation(int i, int j, int isTrue, char[]exp, long[][][]dp){
		if(i>j)return 0l;
		
		if(i==j){
			if(isTrue==1){
				return (exp[i]=='T')?1l:0l;
			}else{
				return (exp[i]=='F')?1l:0l;
			}
		}
		if(dp[i][j][isTrue]!=-1)return dp[i][j][isTrue];
		
		long ways=0;
		for(int idx=i+1;idx<=j-1;idx+=2){
			long lt = booleanEvaluation(i,idx-1,1,exp,dp); //(isTrue==1)means we need true from left.
			long lf = booleanEvaluation(i,idx-1,0,exp,dp);
			long rt = booleanEvaluation(idx+1,j,1,exp,dp);
			long rf = booleanEvaluation(idx+1,j,0,exp,dp);
			
			if(exp[idx]=='&'){
				if(isTrue==1){
					ways = ways + (lt*rt);
					ways = ways%mod;
				}else{
					ways = ways + lf*rt + lt*rf + lf*rf; 
					ways = ways%mod;
				}
			}else if(exp[idx]=='|'){
				if(isTrue==1){
					ways = ways + lt*rt+ lf*rt + lt*rf;
					ways = ways%mod;
				}else{
					ways = ways + lf*rf;
					ways = ways%mod;
				}
			}else{
				if(isTrue==1){
					ways = ways + lf*rt + lt*rf;
					ways = ways%mod;
				}else{
					ways = ways + lt*rt + lf*rf;
					ways = ways%mod;
				}
			}
		}
		
		return dp[i][j][isTrue] = ways;
	}    
------------------------------------------------------------------------------------------------
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];

	}
-> Can also be done using subsequence type problem (take/notTake)
 public int RodCutting(int idx,int len,int[]price,int[][]dp){
        if(idx == 0){
            return len * price[idx];
        }
        
        if(dp[idx][len]!=-1) return dp[idx][len];
        
        int notTake = 0 + RodCutting(idx-1,len,price,dp);
        
        int take = Integer.MIN_VALUE;
        int rodLength = idx+1;
        
        if(rodLength <= len){
            take = price[idx] + RodCutting(idx,len-rodLength,price,dp);
        }
        return dp[idx][len] = Math.max(notTake,take);
    }
------------------------------------------------------------------------------------------------
62. Minimum Insertion Steps to Make a String Palindrome (LC-1312)
Intuition:
-> We basically keep the longest palidromic portion intact.
-> ans would be => (str.length() - longestPalindromicSubsequence(str,rev(str)));
------------------------------------------------------------------------------------------------
63. Shortest Common SuperSequence (basically merge both of the sequence to form one sequence)
a = brute, b = groot;
ans = bgruoote (len=8 which is minimum)
-> ans would be => (len(a)+len(b)-lcs(a,b));

=> To Print 

// after computing LCS use same logic of printing LCS.(using lcs table)
        int i=m;
        int j=n;
        
        StringBuilder sb = new StringBuilder();
        
        while(i>0 && j>0){
            if(c1[i-1]==c2[j-1]){
                sb.append(c1[i-1]);
                i--;
                j--;
            }else if(dp[i-1][j]>=dp[i][j-1]){
                sb.append(c1[i-1]);
                i--;
            }else if(dp[i-1][j]<dp[i][j-1]){
                sb.append(c2[j-1]);
                j--;
            }
        }
        
        while(i>0){sb.append(c1[i-1]);i--;};
        while(j>0){sb.append(c2[j-1]);j--;};
        
        return sb.reverse().toString();

------------------------------------------------------------------------------------------------
64. Jump Game All types (in leetcode)
------------------------------------------------------------------------------------------------
65. Word Wrap
------------------------------------------------------------------------------------------------
66. Largest Divisible subset 
-> Based on LIS
 public List<Integer> largestDivisibleSubset(int[] nums) {
        List<Integer> ans =new ArrayList<>();
        int n=nums.length;
        
        Arrays.sort(nums);
        
        int[]count=new int[n]; //count[i] will store the maximum length of divisible subset upto ith index
        int[]prev=new int[n]; //it will store the prev index that was taken to make the
                            // largest divisible subset upto ith index;
        
        int max=Integer.MIN_VALUE;
        int index=0;
        
        for(int i=0;i<n;i++){
            count[i]=1;
            prev[i]=-1; 
            
            for(int j=i-1;j>=0;j--){
                if(nums[i]%nums[j]==0){
                    if(count[j]+1>count[i]){
                        count[i]=count[j]+1;
                        prev[i]=j;
                    }
                }
            }
            if(max<count[i]){
                index=i;
                max=count[i];
            }
        }
        
        while(index!=-1){
            ans.add(0,nums[index]);
            index=prev[index];
        }
        return ans;
    }

------------------------------------------------------------------------------------------------
67. Min Cost to cut a stick (LC-1547)

public int minCost(int n, int[] cuts) {
      // cuts array should be sorted in order to independently handle partitions

		// here n is the size of stick
		List<Integer> list = new ArrayList<>();
		list.add(0);
		for(int val:cuts)list.add(val);
		list.add(n);
		
		int size = cuts.length; //size of original cuts array
	
		cuts = list.stream().mapToInt(i -> i).toArray();
			
		Arrays.sort(cuts);
	
		int[][] dp = new int[size + 1][size + 1];

		for (int[] dpp : dp)
			Arrays.fill(dpp, -1);

		return minCost(1, size, cuts, dp);
        
    }
    public int minCost(int i, int j, int[]cuts, int[][]dp){
        if(i>j)return 0;
        
        if(dp[i][j]!=-1)return dp[i][j];
        
        int min = Integer.MAX_VALUE;
            
        for(int idx=i;idx<=j;idx++){
            int cost = cuts[j+1] - cuts[i-1]; // will give size of curr rem stick
            
            cost+= minCost(i,idx-1,cuts,dp)+minCost(idx+1,j,cuts,dp);
            min = Math.min(min,cost);
        }
        return dp[i][j] = min;
    }
------------------------------------------------------------------------------------------------
68. Partition Array for Maximum Sum (LC_1043)
-> 

 //front partition problem
    public int maxSumAfterPartitioning(int[]arr,int idx,int k,int[]dp){
        if(idx==arr.length)return 0;
        
        if(dp[idx]!=-1)return dp[idx];
        
        int maxAns = Integer.MIN_VALUE;
        int len = 0;
        int max = Integer.MIN_VALUE;
        
        for(int j=idx;j<Math.min(arr.length,idx+k);j++){
            len++;
            max = Math.max(max,arr[j]);
            
            int sum = len*max + maxSumAfterPartitioning(arr,j+1,k,dp);
            
            maxAns = Math.max(maxAns,sum);
        }
        return dp[idx] = maxAns;
    }
------------------------------------------------------------------------------------------------
69. Russian Doll Envelopes (LC-354)

-> LIS Approach -> https://leetcode.com/problems/russian-doll-envelopes/discuss/2071477/Java-PythonBest-Explanation-with-Pictures

=> Sort according to width but if width is same then dec order of height
why dec order of height?
1. In order to fit one envelop into another we need (w1<w2 && h1<h2).
2. So, if you sort acc to width then you just have height to compare for LIS, and if you sort the height
in inc order then same width will be counted more than one, but it should not.
for eg [[3,5],[6,7],[6,10],[7,11],[8,4]]
-> in above case if i apply lis on height then [6,7] and [6,10] both will be counted but only one should be counted.
That is the reason if w1==w2 then sort in dec order of height.

env[i] = [wi,hi] (width, height)
public int maxEnvelopes(int[][] env) {
        
        Arrays.sort(env,(a,b)->(a[0]==b[0])?b[1]-a[1]:a[0]-b[0]);
        
        int n = env.length;
        
        int[]lis = new int[n+1];
        
        Arrays.fill(lis,Integer.MAX_VALUE);
        lis[0] = Integer.MIN_VALUE;
        
        
        int ans=0;
        for(int i=0;i<n;i++){
            int val = env[i][1];
            int idx = lowerBound(lis,env[i][1]);
            ans = Math.max(idx,ans);
            if(lis[idx]>=val){
                lis[idx]=val;
            }
        }
        
        return ans;
    }
    public int lowerBound(int[]dp, int val){
        int l=0, h=dp.length-1;
        int res = 0;
        
        while(l<=h){
            int mid = (l+h)>>1;
            if(dp[mid]<val){
                res=mid;
                l=mid+1;
            }else{
                h=mid-1;
            }
        }
        return res+1;
    }
------------------------------------------------------------------------------------------------
70. Paint House III (LC-1473)

 public int minCost(int[] houses, int[][] cost, int m, int n, int target) {
        int[][][]dp = new int[m+1][m+1][target+1];
        
        
        for(int[][]a:dp){
            for(int[]b:a){
                Arrays.fill(b,-2);
            }
        }
        
        return minCost(houses,cost,0,0,target,m,n,dp);
    }
    public int minCost(int[]houses,int[][]cost,int idx, int lastColor, int nbr_cnt, int len, int colors, int[][][]dp){
        
        if(nbr_cnt<0){
            return -1;
        }
        
        if(idx==len){
            if(nbr_cnt==0)return 0;
            return -1;
        }
        
        if(dp[idx][lastColor][nbr_cnt]!=-2)return dp[idx][lastColor][nbr_cnt];
        
        
        
        if(houses[idx]!=0){
           if(houses[idx]!=lastColor){
               return dp[idx][lastColor][nbr_cnt] = minCost(houses,cost,idx+1,houses[idx],nbr_cnt-1,len,colors,dp); 
           }else{
               return dp[idx][lastColor][nbr_cnt] = minCost(houses,cost,idx+1,houses[idx],nbr_cnt,len,colors,dp);
           }
        }
        
        int ans = Integer.MAX_VALUE;
        boolean possible = false;
        
        for(int color = 0;color<colors;color++){
            int temp = 0;
            
            if(lastColor==color+1){
                temp = minCost(houses,cost,idx+1,color+1,nbr_cnt,len,colors,dp);
            }else{
                temp = minCost(houses,cost,idx+1,color+1,nbr_cnt-1,len,colors,dp);
            }
            
            if(temp!=-1){
                possible=true;
                ans = Math.min(ans,temp + cost[idx][color]);
            }
        }
        
        if(possible){
            dp[idx][lastColor][nbr_cnt] = ans;
        }else{
            dp[idx][lastColor][nbr_cnt] = -1;
        }
        return dp[idx][lastColor][nbr_cnt];
    }
------------------------------------------------------------------------------------------------

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

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

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

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