Intro to Algorithms Unit 11 ReviewDynamic Programming: Principles & Examples

What's Dynamic Programming?

• Optimization technique used to solve complex problems by breaking them down into simpler subproblems
• Stores solutions to subproblems in memory to avoid redundant calculations and improve efficiency
• Applies to problems with overlapping subproblems and optimal substructure
• Builds solutions incrementally by solving subproblems and combining their solutions
• Differs from greedy algorithms as it considers all possible solutions and chooses the optimal one
  • Greedy algorithms make locally optimal choices at each stage without considering future consequences
• Applicable to a wide range of domains (optimization, graph theory, string problems, etc.)
• Reduces time complexity compared to brute force approaches by avoiding redundant calculations

Key Concepts and Terminology

• Overlapping Subproblems: When a larger problem can be broken down into smaller subproblems that are reused multiple times
  • Storing solutions to these subproblems avoids redundant calculations
• Optimal Substructure: When an optimal solution to a problem can be constructed from optimal solutions of its subproblems
• Memoization: Top-down approach where recursive solutions are stored in a lookup table to avoid redundant calculations
• Tabulation: Bottom-up approach where solutions are built iteratively in a table, starting from base cases and working up to the final solution
• State: Set of variables that represent a subproblem and uniquely define its solution
• Recurrence Relation: Equation that expresses the solution to a problem in terms of solutions to its subproblems
• Time Complexity: Measure of how the running time of an algorithm grows with input size
  • DP often reduces time complexity compared to brute force approaches

How DP Works: Step-by-Step

1. Identify the problem as a candidate for DP by checking for overlapping subproblems and optimal substructure
2. Define the state variables that uniquely represent a subproblem
3. Write the recurrence relation expressing the solution in terms of subproblems
4. Determine the base cases for the smallest subproblems
5. Implement the solution using either memoization (top-down) or tabulation (bottom-up)
   • Memoization: Recursively solve subproblems and store solutions in a lookup table
   • Tabulation: Iteratively fill a table with solutions, starting from base cases
6. Optimize space complexity by only storing necessary previous states
7. Reconstruct the optimal solution by backtracking through the solved subproblems

Common DP Patterns

• 0/1 Knapsack: Given a set of items with weights and values, maximize the total value while respecting a weight constraint
• Longest Common Subsequence: Find the longest subsequence common to two sequences
• Shortest Path (on DAGs): Find the shortest path from a starting node to all other nodes in a weighted Directed Acyclic Graph (DAG)
• Coin Change: Find the minimum number of coins needed to make a certain amount, given denominations
• Rod Cutting: Determine the maximum revenue obtainable by cutting a rod into smaller pieces, given a price for each piece length
• Matrix Chain Multiplication: Find the optimal parenthesization of a sequence of matrices to minimize the number of scalar multiplications
• Longest Increasing Subsequence: Find the longest subsequence in an array where elements are in increasing order
• Edit Distance: Compute the minimum number of operations (insert, delete, replace) to transform one string into another

Real-World Applications

• Resource allocation and optimization problems (knapsack, scheduling, etc.)
• Bioinformatics (sequence alignment, DNA folding)
• Natural Language Processing (text segmentation, parsing)
• Computer Vision (image segmentation, object detection)
• Robotics (path planning, control optimization)
• Finance (portfolio optimization, option pricing)
• Network Routing (shortest path, maximum flow)
• Data Compression (Huffman coding, Lempel-Ziv)

Coding Examples and Practice

• Fibonacci Numbers: Compute the nth Fibonacci number

  </>Python
  def fib(n):
      if n <= 1:
          return n
      return fib(n-1) + fib(n-2)

• Longest Palindromic Substring: Find the longest palindromic substring in a string

  </>Python
  def longestPalindrome(s):
      n = len(s)
      dp = [[False] * n for _ in range(n)]
      ans = ""
      for length in range(n):
          for i in range(n - length):
              j = i + length
              if length == 0:
                  dp[i][j] = True
              elif length == 1:
                  dp[i][j] = (s[i] == s[j])
              else:
                  dp[i][j] = (s[i] == s[j] and dp[i+1][j-1])
              if dp[i][j] and length + 1 > len(ans):
                  ans = s[i:j+1]
      return ans

• Practice platforms (LeetCode, HackerRank, Project Euler) offer DP problems to solve and discuss

Tips for Solving DP Problems

• Start by solving the problem recursively to understand its structure
• Identify overlapping subproblems and optimal substructure
• Define the state variables and write the recurrence relation
• Implement the solution using memoization or tabulation
• Analyze time and space complexity
• Consider if the problem can be solved using a greedy approach
• Practice regularly to recognize common patterns and develop intuition
• Break down complex problems into simpler subproblems
• Use clear variable names and comments to make your code readable

Comparing DP to Other Techniques

• Brute Force: DP is often faster than brute force as it avoids redundant calculations
  • Example: Fibonacci numbers have exponential time complexity with brute force but linear with DP
• Greedy Algorithms: DP considers all possible solutions while greedy algorithms make locally optimal choices
  • Example: Fractional Knapsack can be solved optimally with a greedy approach, but 0/1 Knapsack requires DP
• Memoization vs Tabulation: Memoization is top-down and recursive, while tabulation is bottom-up and iterative
  • Memoization is often easier to implement but may have higher overhead due to recursive calls
  • Tabulation typically has better space complexity as it only stores necessary previous states
• Divide and Conquer: Both break down problems into subproblems, but DP reuses solutions while divide and conquer solves subproblems independently
  • Example: Merge Sort (divide and conquer) vs Longest Common Subsequence (DP)