Review: Dynamic Programming Problems

Dynamic programming problems scare me A LOT.

Yeah, it could be quite frustrating, if you haven’t found the key assertions.

---

---

Dynamic Programming is an algorithmic paradigm that solves a given complex problem by breaking it into subproblems and stores the results of subproblems to avoid computing the same results again.

The main idea behind DP is to save duplicated caculations.

Trade space for time.

---

Basic Abstractions

Name	Summary
Optimal Substructure
DP vs recursive+memoization
Non-linear dynamic problem problems	Leetcode: Minimum Score Triangulation of Polygon

Questions

Name	Example
DP needs only O(1) space	LintCode: Computer Maintenance
Some initialization can be skipped	Leetcode: Longest Arithmetic Subsequence of Given Difference
Some initialization can be skipped	Leetcode: Bomb Enemy
Instead of left-to-right, do it from right-to-left	Maximum Length of Repeated Subarray, Leetcode: Largest Sum of Averages
2-D dp, instead of one	Leetcode: Longest Common Subsequence, Leetcode: Edit Distance
DP breaks down into two subproblems, instead of one	Leetcode: Minimum Score Triangulation of Polygon
Instead of based on possible actions, based on states	Leetcode: Best Time to Buy and Sell Stock with Cooldown
dp + binarytree	Leetcode: Binary Trees With Factors
Ugly Number II	Leetcode: Ugly Number II

Key Parts In DP Problems:

1. Key observation is crucial. Watch careful for how the states transit?
2. Walk through with smaller cases manually. And detect the pattern.

---

Different Types Of DP Functions:

• Interesting dp funcitons
  Domino and Tromino Tiling
  dp(i) = dp(i-1)+dp(i-2)+2*(dp(i-3)+dp(i-4)+…+dp(0))
• DP saves intermediate results, not the final ones
  Champagne Tower
• dp(i) = min(dp(i), dp[i-coin[j]]+1)
  Coin Change
• Function: f(i, j): Longest Palindromic Subsequence
• Coin Change 2
• Save the base case: Maximum Length of Repeated Subarray

---

The most impressive problems to me:

• Min Cost Climbing Stairs
• Maximum Length of Repeated Subarray

---

• CheatSheet: Leetcode For Code Interview
• CheatSheet: Common Code Problems & Follow-ups

See all dynamicprogramming problems: #dynamicprogramming

• Review: Dynamic Programming Problems
• LintCode: Minimum Cycle Section
• LintCode: Frog Jump
• Lintcode: Digital Flip
• LintCode: Computer Maintenance
• LintCode: Card Game
• Leetcode: Zuma Game
• Leetcode: Word Break
• Leetcode: Wildcard Matching
• Leetcode: Video Stitching

See more blog_posts.

---