Introduction to Dynamic Programming

Understanding Dynamic Programming

Dynamic Programming (DP) is a method for solving complex problems by breaking them down into simpler subproblems. It is applicable where the problem can be divided into overlapping subproblems and has optimal substructure. DP is often used for optimization problems and is known for its efficiency in solving recursive problems by storing intermediate results to avoid redundant calculations.

Example 1: Fibonacci Sequence

The Fibonacci sequence is a classic example of dynamic programming. Each number in the sequence is the sum of the two preceding ones, starting from 0 and 1. DP can be used to calculate Fibonacci numbers efficiently by storing previously computed values.

        class Fibonacci {
          static int fib(int n) {
            int[] f = new int[n+2];
            f[0] = 0;
            f[1] = 1;
            for (int i = 2; i <= n; i++) {
              f[i] = f[i-1] + f[i-2];
            }
            return f[n];
          }
          public static void main(String args[]) {
            int n = 9;
            System.out.println(fib(n));
          }
        }
      

34

Example 2: Longest Common Subsequence

The Longest Common Subsequence (LCS) problem is another example where dynamic programming is applied. Given two sequences, the task is to find the length of their longest subsequence present in both.

        class LCS {
          static int lcs(char[] X, char[] Y, int m, int n) {
            int[][] L = new int[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] = Math.max(L[i-1][j], L[i][j-1]);
              }
            }
            return L[m][n];
          }
          public static void main(String args[]) {
            String s1 = "AGGTAB";
            String s2 = "GXTXAYB";
            char[] X = s1.toCharArray();
            char[] Y = s2.toCharArray();
            System.out.println(lcs(X, Y, X.length, Y.length));
          }
        }
      

4

Example 3: 0/1 Knapsack Problem

The 0/1 Knapsack problem is a famous problem in combinatorial optimization. Given weights and values of n items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack.

        class Knapsack {
          static int knapSack(int W, int wt[], int val[], int n) {
            int[][] K = new int[n+1][W+1];
            for (int i = 0; i <= n; i++) {
              for (int w = 0; w <= W; w++) {
                if (i == 0 || w == 0)
                  K[i][w] = 0;
                else if (wt[i-1] <= w)
                  K[i][w] = Math.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];
          }
          public static void main(String args[]) {
            int val[] = new int[]{60, 100, 120};
            int wt[] = new int[]{10, 20, 30};
            int W = 50;
            int n = val.length;
            System.out.println(knapSack(W, wt, val, n));
          }
        }
      

220

Example 4: Matrix Chain Multiplication

Matrix Chain Multiplication is a problem of finding the most efficient way to multiply a given sequence of matrices. The problem is not about multiplying matrices but finding the optimal order to multiply them.

        class MatrixChain {
          static int MatrixChainOrder(int p[], int n) {
            int[][] m = new int[n][n];
            for (int i = 1; i < n; i++)
              m[i][i] = 0;
            for (int L = 2; L < n; L++) {
              for (int i = 1; i < n - L + 1; i++) {
                int j = i + L - 1;
                if (j == n) continue;
                m[i][j] = Integer.MAX_VALUE;
                for (int k = i; k <= j - 1; k++) {
                  int q = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];
                  if (q < m[i][j])
                    m[i][j] = q;
                }
              }
            }
            return m[1][n-1];
          }
          public static void main(String args[]) {
            int arr[] = new int[]{1, 2, 3, 4};
            int size = arr.length;
            System.out.println(MatrixChainOrder(arr, size));
          }
        }
      

18

Example 5: Edit Distance

The Edit Distance problem involves finding the minimum number of operations required to convert one string into another. Operations include insertion, deletion, or substitution of a single character.

        class EditDistance {
          static int editDist(String str1, String str2, int m, int n) {
            int[][] dp = new int[m+1][n+1];
            for (int i = 0; i <= m; i++) {
              for (int j = 0; j <= n; j++) {
                if (i == 0)
                  dp[i][j] = j;
                else if (j == 0)
                  dp[i][j] = i;
                else if (str1.charAt(i-1) == str2.charAt(j-1))
                  dp[i][j] = dp[i-1][j-1];
                else
                  dp[i][j] = 1 + Math.min(dp[i][j-1], Math.min(dp[i-1][j], dp[i-1][j-1]));
              }
            }
            return dp[m][n];
          }
          public static void main(String args[]) {
            String str1 = "sunday";
            String str2 = "saturday";
            System.out.println(editDist(str1, str2, str1.length(), str2.length()));
          }
        }
      

3