Priyanshu Tiwari
by Priyanshu Tiwari
5 min read

Categories

Tags

Table Of Content

Dynamic Programming is an optimization over plain recursion. In this, we re-use the solutions of subproblems for overlapping subproblems

Two types are

1. Memoization - Top Down

No of dimenstions $rightarrow$ No of changing params in the recursive call. Will reduce the time complexity from $O(2^n)$ to $O(n)$.

int memo[n+1];
memset(memo, -1, sizeof(memo));

int fib(int n){

  if(memo[n] == -1)
    memo[n] == (n == 0 || n==1) ? n : fib(n-1) + fib(n-2);
  return memo[n];

}

2. Tabulation - Bottom Up

Doesn’t consume space in stack for recursion calls.

int fib(int n){

  int f[n+1];
  f[0] = 0, f[1] = 1;

  for(int i=2; i<=n; i++)
    f[i] = f[i-i] + f[i-2];
  
  return f[n];

}

Applications #

Utitlity Algorithm
Git Diff LCS
Close Search Edit distance
Shortest Path Bellman Ford, Floyd Warshall
Resource Allocation 0-1 knapsack

Problem #

Longest Common Subsequences #

Given two sequences, find the length of longest subsequence present in both of them.

    int longestCommonSubstr (string S1, string S2, int n, int m)
    {
    if(n == 0 || m == 0) 
        return 0;
        
    if(S1[n-1] == S2[m-1]) 
        return 1 + longestCommonSubstr(S1, S2, n-1, m-1);
    
    return max(longestCommonSubstr(S1, S2, n, m-1), longestCommonSubstr(S1, S2, n-1, m));
    }

Time Complexity: $O(2^n)$

  • Memoization
int lcs( string s1, string s2, int m, int n, vector<vector<int> >& dp){

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

  if(m == 0 || n == 0) 
    return 0;
    
  if (s1[m-1] == s2[n-1])
    return dp[m][n] = 1 + lcs(s1, s2, m-1, n-1);
    
  return dp[m][n] = max(lcs(s1, s2, m-1, n), lcs(s1, s2, m, n-1));
  
}

Time Complexity: $O(m \times n)$

Auxiliary Space: $O(m \times n)$

  • Tabulation
int lcs(int m, int n, string X, string Y)
{
  int L[m+1][n+1];
        
  for (int i=0; i<=m; i++)
    for (int j=0; j<=n; j++)
      {
        if (i == 0 || j == 0)
          L[i][j] = 0;
        else if (X[i-1] == Y[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];
}

Time Complexity: $O(m \times n)$

Auxiliary Space: $O(m \times n)$

  • Space Optimized
int lcs(int m, int n, string X, string Y)
{
 
    int L[2][n + 1];
 
    bool index;
 
    for (int i = 0; i <= m; i++)
    {
        index = i & 1;

        for (int j = 0; j <= n; j++)
        
            if (i == 0 || j == 0)
                L[index][j] = 0; 
            else if (X[i-1] == Y[j-1])
                 L[index][j] = L[1 - index][j - 1] + 1;
            else
                L[index][j] = max(L[1 - index][j],
                               L[index][j - 1]);
    }
    return L[index][n];
}

Time Complexity: $O(m \times n)$

Auxiliary Space: $O(n)$

Coin Change #

Given a value N, find the number of ways to make change for N cents, if we have infinite supply of each of $S = { S1, S2, .. , SM }$ valued coins.

  • Naive
    long long int count(int S[], int m, int n) {
        
    long long int i, j,x,y,table[n + 1][m];
    
    for (i = 0; i < m; i++)
        table[0][i] = 1;
 
    for (i = 1; i < n + 1; i++)
    {
        for (j = 0; j < m; j++)
        {
            x = (i-S[j] >= 0) ? table[i - S[j]][j] : 0;
            y = (j >= 1) ? table[i][j - 1] : 0;
            table[i][j] = x + y;
        }
    }
    return table[n][m - 1];
    }
  • Optimal