Dynamic Programming

𝐍𝐮𝐦𝐛𝐞𝐫 𝐨𝐟 𝐔𝐧𝐢𝐪𝐮𝐞 𝐏𝐚𝐭𝐡𝐬
*Given a A X B matrix with your initial position at the top-left cell, find the number of possible unique paths to reach the bottom-right cell of the matrix from the initial position.
Note: Possible moves can be either down or right at any point in time, i.e., we can move to matrix[i+1][j] or matrix[i][j+1] from matrix[i][j].*

Sol :
int ans(int a,int b){
  int dp[a][b];
  for(int i=0;i<a;i++){
    dp[i][0]=1;
  }
  for(int i=0;i<b;i++){
    dp[0][i]=1;
  }
  for(int i=1;i<a;i++){
    for(int j=1;j<b;j++){
        dp[i][j]=dp[i-1][j]+dp[i][j-1];
  }}
  return dp[a-1][b-1];
}

𝐂𝐨𝐮𝐧𝐭 𝐰𝐚𝐲𝐬 𝐭𝐨 𝐫𝐞𝐚𝐜𝐡 𝐭𝐡𝐞 𝐧’𝐭𝐡 𝐬𝐭𝐚𝐢𝐫:
int countWaysUtil(int n, int m)
{
    int res[n];
    res[0] = 1;
    res[1] = 1;
    for(int i = 2; i < n; i++)
    {
       res[i] = 0;
       for(int j = 1; j <= m && j <= i; j++)
          res[i] += res[i - j];
    }
    return res[n - 1];
}
int countWays(int s, int m)
{
    return countWaysUtil(s + 1, m);
}

𝐌𝐚𝐱𝐢𝐦𝐢𝐳𝐞 𝐓𝐡𝐞 𝐂𝐮𝐭 𝐒𝐞𝐠𝐦𝐞𝐧𝐭𝐬:
int maximizeTheCuts(int n, int x, int y, int z)
    {
        if(n==0) return 0;
        int one = (n-x)>0?maximizeTheCuts(n-x,x,y,z):0;
        int two = (n-y)>0?maximizeTheCuts(n-y,x,y,z):0;
        int three = (n-z)>0?maximizeTheCuts(n-z,x,y,z):0;
        return 1+max(one,max(two,three));
    }

𝐌𝐢𝐧𝐢𝐦𝐮𝐦 𝐧𝐮𝐦𝐛𝐞𝐫 𝐨𝐟 𝐣𝐮𝐦𝐩𝐬:
int minJumps(int arr[], int n){
        if(arr[0]==0 || n==0) return -1;
        int dp[n];
        for(int i=0;i<n;i++){
            dp[i]=INT_MAX;
        }
        dp[0]=0;
        for(int i=1;i<n;i++){
            for(int j=0;j<i;j++){
                if(i<=j+arr[j] && dp[i]!=INT_MAX){
                    dp[i]=min(dp[i],dp[j]+1);
                }
            }  
        }
        return dp[n-1];
    }
    
  𝐓𝐨𝐭𝐚𝐥 𝐃𝐞𝐜𝐨𝐝𝐢𝐧𝐠 𝐌𝐞𝐬𝐬𝐚𝐠𝐞𝐬:
  int countDecodingDP(char *digits, int n)
{
    int count[n+1];
    count[0] = 1;
    count[1] = 1;
    if(digits[0]=='0') 
         return 0;
    for (int i = 2; i <= n; i++)
    {
        count[i] = 0;
        if (digits[i-1] > '0')
            count[i] = count[i-1];
        if (digits[i-2] == '1' ||
              (digits[i-2] == '2' && digits[i-1] < '7') )
            count[i] += count[i-2];
    }
    return count[n];
}

𝐋𝐨𝐧𝐠𝐞𝐬𝐭 𝐂𝐨𝐦𝐦𝐨𝐧 𝐒𝐮𝐛𝐬𝐞𝐪𝐮𝐞𝐧𝐜𝐞:
int lcs(int m, int n, string s1, string s2)
    {
       int L[m + 1][n + 1]; 
       int i, j; 
       for (i = 0; i <= m; i++) 
        { 
        for (j = 0; j <= n; j++) 
        { 
        if (i == 0 || j == 0) 
            L[i][j] = 0; 
        else if (s1[i - 1] == s2[j - 1]) 
            L[i][j] = L[i - 1][j - 1] + 1; 
        else
            L[i][j] = max(L[i - 1][j], L[i][j - 1]); 
        } 
    }
    return L[m][n]; 
    }
    
𝐂𝐨𝐧𝐬𝐞𝐜𝐮𝐭𝐢𝐯𝐞 𝟏'𝐬 𝐧𝐨𝐭 𝐚𝐥𝐥𝐨𝐰𝐞𝐝:
ll countStrings(int n) {
	    ll a[n];
	    ll b[n];
	    a[0]=1;
	    b[0]=1;
	    for(int i=1;i<n;i++){
	        a[i]=a[i-1]+b[i-1];
	        b[i]=b[i-1];
	    }
	    return a[n-1]+b[n-1];
	}
  
𝐄𝐝𝐢𝐭 𝐃𝐢𝐬𝐭𝐚𝐧𝐜𝐞:
int editDistance(string a,string b,int n,int m){
    int dp[n+1][m+1];
    for(int i=0;i<n+1;i++){
    for(int j=0;j<m+1;j++){
      if(n==0){
        dp[i][j] = j;
      }
      else if(m==0){
        dp[i][j]=i;
      }
      else if(a[i-1]==b[j-1]){
        dp[i][j] = dp[i-1][j-1];
      }
      else{
        dp[i][j] = 1 + + min(dp[i][j - 1],dp[i - 1][j], dp[i - 1][j - 1]);
      }     
    }
    }
    return dp[n][m];
}

𝐑𝐨𝐝 𝐂𝐮𝐭𝐭𝐢𝐧𝐠:
int cutRod(int price[], int n)
{
   int val[n+1];
   val[0] = 0;
   int i, j;
   for (i = 1; i<=n; i++)
   {
       int max_val = INT_MIN;
       for (j = 0; j < i; j++)
         max_val = max(max_val, price[j] + val[i-j-1]);
       val[i] = max_val;
   }
   return val[n];
}

𝐋𝐨𝐧𝐠𝐞𝐬𝐭 𝐈𝐧𝐜𝐫𝐞𝐚𝐬𝐢𝐧𝐠 𝐒𝐮𝐛𝐬𝐞𝐪𝐮𝐞𝐧𝐜𝐞:
int lis(int arr[], int n)
{
    int lis[n];
    lis[0] = 1;
    for (int i = 1; i < n; i++) {
        lis[i] = 1;
        for (int j = 0; j < i; j++)
            if (arr[i] > arr[j] && lis[i] < lis[j] + 1)
                lis[i] = lis[j] + 1;
    }
    return *max_element(lis, lis + n);
}

𝐌𝐚𝐱𝐢𝐦𝐮𝐦 𝐬𝐮𝐦 𝐢𝐧𝐜𝐫𝐞𝐚𝐬𝐢𝐧𝐠 𝐬𝐮𝐛𝐬𝐞𝐪𝐮𝐞𝐧𝐜𝐞:
int maxSumIS(int arr[], int n)  
	{ 
	    int dp[n];
	    dp[0]=arr[0];
	    for(int i=1;i<n;i++){
	        dp[i]=arr[i];
	        for(int j=0;j<i;j++){
	            if(arr[j]<arr[i] && dp[i]<dp[j]+arr[i]){
	                dp[i]=dp[j]+arr[i];
	            }
	        }
	    }
	    return *max_element(dp,dp+n);
	}
	
𝐌𝐚𝐱 𝐥𝐞𝐧𝐠𝐭𝐡 𝐜𝐡𝐚𝐢𝐧:
int maxChainLen(struct val p[],int n)
{
    int dp[n];
    int i,j=0;
    for ( i = 0; i < n; i++ )
        dp[i] = 1;
    for ( i = 1; i < n; i++ )
        for ( j = 0; j < i; j++ )
            if ( p[i].first > p[j].second &&
                    dp[i] < dp[j] + 1)
                dp[i] = dp[j] + 1;
    int max=0;
    for ( i = 0; i < n; i++ )
        if ( max < dp[i] )
            max = dp[i];
  return max;
}

𝐖𝐚𝐭𝐞𝐫 𝐎𝐯𝐞𝐫𝐟𝐥𝐨𝐰:
double waterOverflow(int K, int R, int C) {
        double glass[(R*(R-1))/2];
        memset(glass,0,sizeof(glass));
        glass[0]=K;
        for(int i=1;i<R;i++){
            for(int j=1;j<i;j++){
                int x = glass[i];
                if(x<=1.0){
                    x=0;
                }
                else{
                    x = x-1.0;
                }
                if(x){
                    x = x/2;
                    glass[i+1]+=x;
                    glass[i+2]+=x;
                }
                return glass[(i*(i-1))/2 + j-1];
            }
        }
    }
    
𝐌𝐚𝐱𝐢𝐦𝐮𝐦 𝐓𝐢𝐩 𝐂𝐚𝐥𝐜𝐮𝐥𝐚𝐭𝐨𝐫:
    if (n == 0)
        return 0;
    if (x != 0 and y != 0)
        return max(
            arr1[n - 1] + maxTip(arr1, arr2, n - 1,x - 1, y),arr2[n - 1] + maxTip(arr1, arr2, n - 1, x,y - 1));
    if (y == 0)
        return arr1[n - 1] + maxTip(arr1, arr2, n - 1,  x - 1, y);
    else
        return arr2[n - 1] + maxTip(arr1, arr2, n - 1, x, y - 1);
}

𝟎 - 𝟏 𝐊𝐧𝐚𝐩𝐬𝐚𝐜𝐤 𝐏𝐫𝐨𝐛𝐥𝐞𝐦:
int knapSack(int W, int wt[], int val[], int n)
{
    int i, w;
    vector<vector<int>> K(n + 1, vector<int>(W + 1));
    for(i = 0; i <= n; i++)
    {
        for(w = 0; w <= W; w++)
        {
            if (i == 0 || w == 0)
                K[i][w] = 0;
            else if (wt[i - 1] <= w)
                K[i][w] = max(val[i - 1] +
                                K[i - 1][w - wt[i - 1]],
                                K[i - 1][w]);
            else
                K[i][w] = K[i - 1][w];
        }
    }
    return K[n][W];
}