Dynamic Programing

Here's the breakdown of common DP patterns and their subprblems. I highlighted the keywords that indicate it's likely a dynamic programming problem.

Sequence This is the most common type of DP problem and a good place to get a feel of dynamic programming. In the recurrence relation,dp[i] normally means max/min/best value for the sequence ending at index i.

House robber - find maximum amount of loot Coin change - find minimum amount of coins needed to make up an amount

Grid This is the 2D version of the sequence DP. dp[i][j] means max/min/best value for matrix cell ending at index i, j.

Robot unique paths - number of ways for robot to move from top left to bottom right Min path sum - find path in a grid with minimum cost Maximal square - find maximal square of 1s in a grid of 0s and 1s

Dynamic number of subproblems This is similar to "Sequence DP" except dp[i] depends on a dynamic number of subproblems, e.g. dp[i] = max(d[j]..) for j from 0 to i.

Longest Increasing Subsequence - find the longest increasing subsequence of an array of numbers Buy/sell stock with at most K transactions - maximize profit by buying and selling stocks using at most K transaction

Partition This is a continuation of DFS + memoization problems. These problems are easier to reason and solve with a top-down approach. The key to solve these problems is to draw the state-space tree and then traverse it.

Decode ways - how many ways to decode a string Word break - partition a word into words in a dictionary Triangle - find the smallest sum path to traverse a triangle of numbers from top to bottom Partition to Equal Sum Subsets - partition a set of numbers into two equal-sum subsets

Two Sequences This type of problem has two sequences in their problem statement. dp[i][j] represents the max/min/best value for the first sequence ending in index i and second sequence ending in index j.

Edit distance - find the minimum distance to edit one string to another Longest common subsequence - find the longest common subsequence that is common in two sequences

Game theory This type of problem asks for whether a player can win a decision game. The key to solving game theory problems is to identify the winning state, and formulating a winning state as a state that returns a losing state to the opponent

Coins in a line Divisor game Stone game

Range dp[i][j] here means the best way to get optimal results using elements in range [i..j]. Bursting balloons

Read more about intro to DP https://algo.monster/problems/dynamic_programming_intro and other patterns summarized here https://algo.monster/problems/stats

解題步驟:

先用紙筆畫一下自己人工會怎麼處理這個問題，往切割成子問題的方向走。 先想到recursion的解法。

核心概念: 1, 如何衰減問題，切割成子問題。 2. 當問題衰減到極致(base case) 答案為何? memorization 減少重複計算 (array, hashMap)

根據填寫array的方式，看是否可以減少維度or不需要memeoriztion只要兩個變數重複使用?

Button up (Recommended) : easy to compute the complexity

dp array-

Button up的關鍵就是定義出好用的dp[]

有幾個常見的組合

  • dp[i] 表示滿足某條件的數目，其中i為另一個用來切割成子問題用的state。

    • ex. i表示ended with array[i]

    • ex. i表示started with array[i]

找到important factor which you want to bring to the next state and set that factor as one of dimensions

  • It is very common and useful to add prefix and subfix to the array in order to simply the computation

    • 312. Burst Balloons

This post will walk you through the THINKING process behind Dynamic Programming so that you can solve these questions on your own.

  1. Category Most dynamic programming questions can be boiled down to a few categories. It's important to recognize the category because it allows us to FRAME a new question into something we already know. Frame means use the framework, not copy an approach from another problem into the current problem. You must understand that every DP problem is different.

    Question: Identify this problem as one of the categories below before continuing.

    • 0/1 Knapsack

    • Unbounded Knapsack

    • Shortest Path (eg: Unique Paths I/II)

    • Fibonacci Sequence (eg: House Thief, Jump Game)

    • Longest Common Substring/Subsequeunce

    Answer: 0/1 Knapsack

    Why 0/1 Knapsack? Our 'Capacity' is the target we want to reach 'S'. Our 'Items' are the numbers in the input subset and the 'Weights' of the items are the values of the numbers itself. This question follows 0/1 and not unbounded knapsack because we can use each number ONCE.

    What is the variation? The twist on this problem from standard knapsack is that we must add ALL items in the subset to our knapsack. We can reframe the question into adding the positive or negative value of the current number to our knapsack in order to reach the target capacity 'S'.

  2. States What variables we need to keep track of in order to reach our optimal result? This Quora post explains state beautifully, so please refer to this link if you are confused: www.quora.com/What-does-a-state-represent-in-terms-of-Dynamic-Programming

    Question: Determine State variables. Hint: As a general rule, Knapsack problems will require 2 states at minimum.

    Answer: Index and Current Sum Why Index? Index represents the index of the input subset we are considering. This tells us what values we have considered, what values we haven't considered, and what value we are currently considering. As a general rule, index is a required state in nearly all dynamic programming problems, except for shortest paths which is row and column instead of a single index but we'll get into that in a seperate post.

    Why Current Sum? The question asks us if we can sum every item (either the positive or negative value of that item) in the subset to reach the target value. Current Sum gives us the sum of all the values we have processed so far. Our answer revolves around Current Sum being equal to Target.

  3. Decisions Dynamic Programming is all about making the optimal decision. In order to make the optimal decision, we will have to try all decisions first. The MIT lecture on DP (highly recommended) refers to this as the guessing step. My brain works better calling this a decision instead of a guess. Decisions will have to bring us closer to the base case and lead us towards the question we want to answer. Base case is covered in Step 4 but really work in tandem with the decision step.

    Question: What decisions do we have to make at each recursive call? Hint: As a general rule, Knapsack problems will require 2 decisions.

    Answer: This problem requires we take ALL items in our input subset, so at every step we will be adding an item to our knapsack. Remember, we stated in Step 2 that "The question asks us if we can sum every item (either the positive or negative value of that item) in the subset to reach the target value." The decision is:

    1. Should we add the current numbers positive value

    2. Should we add the current numbers negative value

    As a note, knapsack problems usually don't require us to take all items, thus a usual knapsack decision is to take the item or leave the item.

  4. Base Case Base cases need to relate directly to the conditions required by the answer we are seeking. This is why it is important for our decisions to work towards our base cases, as it means our decisions are working towards our answer.

    Let's revisit the conditions for our answers.

    1. We use all numbers in our input subset.

    2. The sum of all numbers is equal to our target 'S'.

    Question: Identify the base cases. Hint: There are 2 base cases.

    Answer: We need 2 base cases. One for when the current state is valid and one for when the current state is invalid.

    1. Valid: Index is out of bounds AND current sum is equal to target 'S'

    2. Invalid: Index is out of bounds

    Why Index is out of bounds? A condition for our answer is that we use EVERY item in our input subset. When the index is out of bounds, we know we have considered every item in our input subset.

    Why current sum is equal to target? A condition for our answer is that the sum of using either the positive or negative values of items in our input subet equal to the target sum 'S'.

    If we have considered all the items in our input subset and our current sum is equal to our target, we have successfully met both conditions required by our answer.

    On the other hand, if we have considered all the items in our input subset and our current sum is NOT equal to our target, we have only met condition required by our answer. No bueno.

  5. Code it If you've thought through all the steps and understand the problem, it's trivial to code the actual solution.

     def findTargetSumWays(self, nums, S):
     index = len(nums) - 1
     curr_sum = 0
     return self.dp(nums, S, index, curr_sum)
     
 def dp(self, nums, target, index, curr_sum):
 	# Base Cases
     if index < 0 and curr_sum == target:
         return 1
     if index < 0:
         return 0 
     
 	# Decisions
     positive = self.dp(nums, target, index-1, curr_sum + nums[index])
     negative = self.dp(nums, target, index-1, curr_sum + -nums[index])
     
     return positive + negative

  6. Optimize Once we introduce memoization, we will only solve each subproblem ONCE. We can remove recursion altogether and avoid the overhead and potential of a stack overflow by introducing tabulation. It's important to note that the top down recursive and bottom up tabulation methods perform the EXACT same amount of work. The only different is memory. If they peform the exact same amount of work, the conversion just requires us to specify the order in which problems should be solved. This post is really long now so I won't cover these steps here, possibly in a future post.

Memoization Solution for Reference

class Solution:
    def findTargetSumWays(self, nums, S):
        index = len(nums) - 1
        curr_sum = 0
        self.memo = {}
        return self.dp(nums, S, index, curr_sum)
        
    def dp(self, nums, target, index, curr_sum):
        if (index, curr_sum) in self.memo:
            return self.memo[(index, curr_sum)]
        
        if index < 0 and curr_sum == target:
            return 1
        if index < 0:
            return 0 
        
        positive = self.dp(nums, target, index-1, curr_sum + nums[index])
        negative = self.dp(nums, target, index-1, curr_sum + -nums[index])
        
        self.memo[(index, curr_sum)] = positive + negative
        return self.memo[(index, curr_sum)]

Leave a comment on what DP problems you would like this type of post for next and upvote this solution if you found it helpful. I'd like to get this to the top because I'm honestly tired of seeing straight optimized tabulated solutions with no THINKING process behind it.

DP IS EASY!

Thanks.

Previous881. Boats to Save PeopleNextOthers

Last updated

Was this helpful?