Dynamic Programming Summary - Leetcode

0.Basic Concepts

Dynamic Programming (DP): is a method for solving a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions - ideally, using a memory-based data structure.

1.The difference between DP and divide-and-conquer

Divide-and-conquer partitions the problem into disjoint subproblems while DP partitions the problem into overlapped subproblems.

2.Typical DP problems

• A problem can have many solutions, each solution has a value, try to find the solution with optimal value.
• Try to find the total number of solutions of a problem.

3.Solution

1. Define the structure of an optimal solution.
2. Recursively define the value of an optimal solution.
3. Compute the value of an optimal solution in a bottom-up fashion.
   If we only need the value of the optimal solution, the above 3 steps are enough.
4. Construct an optimal solution from computed information. (Usually, step 4 requires us to maintain some additional information to construct the optimal solution.)

4.Typical Examples (examples are all from Leetcode.com)

I strongly recommend you to read the following two articles: 

http://mp.weixin.qq.com/s?__biz=MzA5MzE4MjgyMw==&mid=2649455129&idx=1&sn=cee7006255efba925f1e7e02034f15e8&scene=5&srcid=07238z0Wz6rbUusBYiKIYv3O#rd

http://love-oriented.com/pack/

[Type 1] find the solution with optimal value 

• [Type 1-1] Index-based based bottom-up method:
  [A typical question 1-1] Given an array arr[], find the continuous subarray which has the maximum sum, output the sum value.
  e.g., [1, -2, 3, 4, -2] -> 7 (becuase 3+4=7)
  
  [How to define dp[i]]
  The "optimal subsolution dp[i]" can be constructed in 2 ways:
      1.dp[i] is the optimal solution for the subarray arr[0:i]
      e.g., in the example, dp = [1,1,3,7,7]
      The output should be dp[arr.length-1], which is 7.
  
      2.dp[i] is the optimal solution whose last element is arr[i] for the subarray arr[0:i] 
      e.g., in the example, dp = [1,-1,3,7,5]
      The output should be maximum value in dp[], which is 7.
      (A brief explanation: dp[1]=-1 is because dp[1] must contain the lase element arr[1], so the subarray can be [1,-2] or [-2], apparently the first subarray's sum is larger. So dp[1] = 1+(-2) = 1.
  
  [Bottom up process] The bottom up process is from i=0 to i=arr.length-1. This is different from value-based problem. We will talk about this later.
  
  [Practice]
• array:

1. [53] Maximum Subarray
2. [152] Maximum Product of Subarray
3. [32] Longest Valid Parentheses
4. [300] Longest Increasing Subsequence
5. [368] Largest Divisible Subset
6. [139] Word Break
• matrix:
1. [120] Triangle
2. [64] Minimum Path Sum
3. [221] Maximal Square
4. [174] Dungeon Game (Note, from bottom right to top left)
5. [354] Russian Doll Envelopes 
6. [363] Max Sum of Rectangle No Larger Than K
7. [32] Longest Valid Parentheses

• [Type 1-2] Index-based bottom-up method, with multiple states.
  [Question 1-2] adds some extra constraints on type 1-1. The constraint might lead to multiple states. Sometimes, solution 1-1 could solve such situation. However, sometimes it does not work.
  
  [Solution 1-2] use extra arrays each corresponding to one condition. (Or add one dimension, e.g., array arr[] ->matrix arr[][], dp[i][0] corresponds to state 0, dp[i][1] corresponds to state 1, etc).
  
  [Practice]

1. [198] House Robber
   ([soln], two states: rob the first house/not, the bottom-up method needs to maintain 2 arrays, one corresponding to "rob the 1st house", another corresponding to "not rob the 1st house". Similarly, we can also maintain a matrix arr[][], arr[i][0] corresponds to "not rob the first house" while arr[i][1] corresponds to "rob the first house".)
2. [213] House Robber II
3. [256] Paint House (3 states/colors)
4. [265] Paint House II (k states/colors)
5. [276] Paint Fence
6. [123] Best Time to Buy and Sell Stock III
7. [188] Best Time to Buy and Sell Stock IV
8. [309] Best Time to Buy and Sell Stock with Cooldown

         dp[start][end] variation: The substructure (subarray) is arr[start:end] rather than arr[0:end]. We can understand in this way: A subarray ending at j can starts from i = 0 to j-1. Each i corresponds to a state. So we should construct dp as dp[i][j], which represents the optimal solution for subarray[i:j].

1. [132] Palindrome Partitioning II
2. [87] Scramble String
3. [312] Burst Balloons

• [Type 1-3] Value-based bottom-up method
  [A typical question 1-3] "Given a number n and an array arr[], try to find the minimum set of numbers from arr whose sum is equal to n".
  
  [How to define dp[i]] dp[i] corresponds to the optimal set whose sum is equal to i.
  
  [Bottom up process] The bottom up process is from i=0 to i=n. This is the biggest difference between index-based problem and value-based problem. In the index-based problem, the bottom up process is from i=0 to i=arr.length-1.
  
  [Practice]

1. [322] Coin Change
2. [279] Perfect Squares
3. [343] Integer Break

[Type 2] Two arrays "match" DP 

This type of questions will give two strings, s1 and s2. The question is whether s1 can be transformed/matched to s2 in a given way. The typical solution is to construct a m*n matrix, check whether s1[:i] can be transformed/matched to s2[:j]. Construct the matrix in a bottom-up way.

[Practice]

1. [54] Regular Expression Match
2. [72] Edit Distance
3. [44] Wildcard Matching
4. [97] Interleaving String

[Type 3] total # of solutions

1. [276] Paint Fence
2. [96] Unique Binary Search Tree
3. [95] Unique Binary Search Trees II
4. [91] Decode ways
5. [62] Unique Path
6. [63] Unique Paths II

[Type 4] Others

1. [338]Counting Bits
2. [264] Ugly Number II
3. [357] Count Numbers with Unique Digits
4. 背包九讲的相关问题