Dynamic Programming

Dynamic Programming (DP) is a powerful technique used to solve problems by breaking them down into simpler subproblems. It is particularly useful for optimization problems where the solution can be built from solutions to subproblems.

Table of Contents

• Table of Contents
• Dynamic Programming Basics
• Common DP Patterns
  • 1. Fibonacci Sequence
  • 2. Climbing Stairs
  • 3. 0/1 Knapsack Problem
  • 4. Longest Common Subsequence (LCS)
  • 5. Coin Change
• Time and Space Complexity
• Related Leetcode Questions
  • Easy
  • Medium
  • Hard

Dynamic Programming Basics

• Definition: DP is a method for solving complex problems by breaking them down into simpler subproblems. It stores the results of subproblems to avoid redundant computations.
• Key Characteristics:
  • Optimal Substructure: The optimal solution to the problem can be constructed from optimal solutions of its subproblems.
  • Overlapping Subproblems: The problem can be broken down into subproblems that are reused multiple times.
• Approaches:
  • Top-Down (Memoization): Solve the problem recursively and store the results of subproblems.
  • Bottom-Up (Tabulation): Solve the problem iteratively by filling up a table.

Common DP Patterns

1. Fibonacci Sequence

• Problem: Compute the nth Fibonacci number.
• Example:

  public int fib(int n) {
      if (n <= 1) return n;
      int[] dp = new int[n + 1];
      dp[0] = 0;
      dp[1] = 1;
      for (int i = 2; i <= n; i++) {
          dp[i] = dp[i - 1] + dp[i - 2];
      }
      return dp[n];
  }

• Time Complexity: O(n)
• Space Complexity: O(n)

2. Climbing Stairs

• Problem: Find the number of distinct ways to climb to the top of a staircase with n steps, where you can climb 1 or 2 steps at a time.
• Example:

  public int climbStairs(int n) {
      if (n == 1) return 1;
      int[] dp = new int[n + 1];
      dp[1] = 1;
      dp[2] = 2;
      for (int i = 3; i <= n; i++) {
          dp[i] = dp[i - 1] + dp[i - 2];
      }
      return dp[n];
  }

• Time Complexity: O(n)
• Space Complexity: O(n)

3. 0/1 Knapsack Problem

• Problem: Given a set of items, each with a weight and a value, determine the maximum value you can carry in a knapsack of a given capacity.
• Example:

  public int knapsack(int[] weights, int[] values, int capacity) {
      int n = weights.length;
      int[][] dp = new int[n + 1][capacity + 1];
      for (int i = 1; i <= n; i++) {
          for (int j = 0; j <= capacity; j++) {
              if (weights[i - 1] <= j) {
                  dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1]);
              } else {
                  dp[i][j] = dp[i - 1][j];
              }
          }
      }
      return dp[n][capacity];
  }

• Time Complexity: O(n * capacity)
• Space Complexity: O(n * capacity)

4. Longest Common Subsequence (LCS)

• Problem: Find the length of the longest subsequence common to two strings.
• Example:

  public int longestCommonSubsequence(String text1, String text2) {
      int m = text1.length(), n = text2.length();
      int[][] dp = new int[m + 1][n + 1];
      for (int i = 1; i <= m; i++) {
          for (int j = 1; j <= n; j++) {
              if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                  dp[i][j] = dp[i - 1][j - 1] + 1;
              } else {
                  dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
              }
          }
      }
      return dp[m][n];
  }

• Time Complexity: O(m * n)
• Space Complexity: O(m * n)

5. Coin Change

• Problem: Find the minimum number of coins needed to make up a given amount.
• Example:

  public int coinChange(int[] coins, int amount) {
      int[] dp = new int[amount + 1];
      Arrays.fill(dp, amount + 1);
      dp[0] = 0;
      for (int i = 1; i <= amount; i++) {
          for (int coin : coins) {
              if (coin <= i) {
                  dp[i] = Math.min(dp[i], dp[i - coin] + 1);
              }
          }
      }
      return dp[amount] > amount ? -1 : dp[amount];
  }

• Time Complexity: O(amount * n) (where n is the number of coins)
• Space Complexity: O(amount)

Time and Space Complexity

Problem	Time Complexity	Space Complexity
Fibonacci Sequence	O(n)	O(n)
Climbing Stairs	O(n)	O(n)
0/1 Knapsack Problem	O(n * capacity)	O(n * capacity)
Longest Common Subsequence	O(m * n)	O(m * n)
Coin Change	O(amount * n)	O(amount)

Related Leetcode Questions

Easy

1. Climbing Stairs
2. House Robber
3. Maximum Subarray

Medium

1. Coin Change
2. Longest Increasing Subsequence
3. Unique Paths

Hard

1. Edit Distance
2. Best Time to Buy and Sell Stock IV
3. Word Break