Session 49: DP Implementation Lab

Original Session

Date: 13 March 2025

Topic: DP

Concept: Recursion + memoization is DP

Concept: Iterative + tabulation is DP

Video: Link here

Programs

1. 62. Unique Paths
   1. leetcode here
   2. Recursive
      1. Base Conditions:
         1. break-point: (i==0 && j==0) return 1; // First cell return 1;
         2. edge-cases: i < 0 || j< 0 return 0; // answer does not exist.
      2. Recursive relation.
         1. up = func(row-1, col)
         2. col = func(row, col-1)
      3. Answer (return statement)
         1. count = top + left.
      4. Time Complexity
         1. 2^m*n
      5. Optimize with 3 Step Process
      6. Build data structure to store.
      7. Store answer in this data structure.
      8. Before recursion check if answer exist, if yes then no need of recursion.
      9. After Memoization
         1. Time Complexity: m*n
         2. Space Complexity: m*n + stack for length of path.
            
            
   3. Iteration (Tabulation)
      1. Base condition in recursive, becomes initiation of tabulation.
      2. Time Complexity is Same
      3. Space complexity is improved because no extra stack for method calls.
         
         

2. 63. Unique Paths II [Recursive approach in video]

3. 72. Edit Distance [Recursive approach in video]
   1. leetcode here

      class Solution {
          
          private int[][] dp = new int[501][501];
      
          private int solve(String s1, String s2, int m, int n) {
              if (m == 0) return n;
              if (n == 0) return m;
              
              if (dp[m][n] != -1) return dp[m][n];
              
              if (s1.charAt(m - 1) == s2.charAt(n - 1)) {
                  return dp[m][n] = solve(s1, s2, m - 1, n - 1);
              } else {
                  int op1 = solve(s1, s2, m, n - 1); // insert
                  int op2 = solve(s1, s2, m - 1, n); // delete
                  int op3 = solve(s1, s2, m - 1, n - 1); // replace
                  
                  return dp[m][n] = Math.min(op1, Math.min(op2, op3)) + 1;
              }
          }
          
          public int minDistance(String word1, String word2) {
              for (int[] row : dp) {
                  Arrays.fill(row, -1);
              }
              return solve(word1, word2, word1.length(), word2.length());
          }
      }

4. 1143. Longest Common Subsequence [Recursive approach InVideo]
   1. leetcode here

      private int[][] dp = new int[1001][1001];
      
          private int solve(String s1, String s2, int i, int j) {
              if (i == 0 || j == 0) return 0;
              
              if (dp[i][j] != -1) return dp[i][j];
              
              if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                  return dp[i][j] = solve(s1, s2, i - 1, j - 1) + 1;
              } else {
                  return dp[i][j] = Math.max(solve(s1, s2, i - 1, j), solve(s1, s2, i, j - 1));
              }
          }
      
          public int longestCommonSubsequence(String text1, String text2) {
              for (int[] row : dp) {
                  Arrays.fill(row, -1);
              }
              return solve(text1, text2, text1.length(), text2.length());
          }