Chapter 10: Dynamic Programming

Contents:

• Dynamic Programming
  • Overview
  • Characteristics
  • Implementation Techniques
  • Applications
  • Benefits
  • Challenges
  • Approaches
  • Complexity Analysis
• 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