Module 12: Dynamic Programming Examples

Contents:

• Max Sum Subarray Problem
  • Introduction
  • Baseline: Brute-force
  • Divide and Conquer Solution
  • Kadane’s Algorithm: Dynamic Programming Solution
• Chain Matrix Multiplication Problem
  • Introduction
  • The Chain Matrix Multiplication Problem
  • Brute-Force Approach
  • Dynamic Programming Approach
• Longest Common Subsequence Problem
  • Introduction
  • Brute Force Approach
  • DP Solution for LCS
  • Traceback to Find the LCS
  • Pseudocode
  • Variations