3.4. Dynamic Programming

Two equivalent approaches to implement dynamic programming are top-down with memoization and bottom-up. Top-down with memoization is like a cached recursive function call, and it is more natural to implement. The speed is sometimes faster than bottom-up approach.

As for the bottom-up approach, the most crucial part is to get the recurrence equation. It tests the math modeling ability of candidates.

DP is normally to resolve optimization problem. For instance, in the following cases, we can consider using dynamic programming?

1. Input cannot sort

2. Find minimum/maximum result

3. Check the feasibility

4. Count all possible solutions

• 3.4.1. Questions
  • 3.4.1.1. Maximum Number of Points with Cost
  • 3.4.1.2. Regular Expression Matching
  • 3.4.1.3. Wildcard Matching
  • 3.4.1.4. Subsequence Number
  • 3.4.1.5. Longest Increasing Subsequence(LIS)
  • 3.4.1.6. Number of Longest Increasing Subsequence(LIS)
  • 3.4.1.7. Longest Common Subsequence
  • 3.4.1.8. Edit Distance (Levenshtein distance)
  • 3.4.1.9. Burst Balloons
  • 3.4.1.10. Paint House
  • 3.4.1.11. House Robber
  • 3.4.1.12. Dungeon Game
  • 3.4.1.13. Target Sum
  • 3.4.1.14. Maximal Square
  • 3.4.1.15. Count Subarrays With More Ones Than Zeros
  • 3.4.1.16. Longest String Chain
  • 3.4.1.17. Warehouses In Villages
  • 3.4.1.18. Maximum Profit in Job Scheduling
  • 3.4.1.19. Longest Increasing Subsequence(LIS)
  • 3.4.1.20. Russian Doll Envelopes
  • 3.4.1.21. Maximum Height by Stacking Cuboids