Chapter 9. Dynamic Programming I

Chapter 9. Dynamic Programming I#

Fibonacci Number#

Fibonacci number uses recursion to solve the subproblem first and then get to its original problem. Strictly speaking, this is not dynamic programming because no maximum/minimum problem is involved. But the idea is very similar.

(7)#\[\begin{align} f(n+2) &= f(n+1) + f(n) \\ f(1) &= 1 \\ f(2) &= 1 \end{align}\]

Naive recursion is not efficient as its time complexity is \(O(n^2)\).

def fibonacci(n):
    if n<=2:
        return 1

    return fibonacci(n-1) + fibonacci(n-2)

# test
print(fibonacci(1))
print(fibonacci(2))
# this will take about 18 seconds
print(fibonacci(40))

1
1

102334155

When we draw the recursion tree, it is easy to find out the reason, which is that there are duplicated subproblems.

For example, when calculating f(20), we have to calculate f(18) and f(19). To calculate f(19), we have to calculate f(18) and f(17). In this way, the subproblem f(18) has been calculated twice. The time complexity of the naive implementation is \(O(n^2)\), because there are \(n\) subproblems, and each subproblem requires \(O(n)\) time.

For duplicated subproblems, we can create a memo, which reduces the complexity to \(O(n)\)

  • once the subproblem is done, we save its results to the memo

  • once the subproblem is needed, we go to the memo first before solving it directly.

def fibonacci(n):
    
    # initialize a memo
    memo = {}
    memo[1] = 1
    memo[2] = 1

    # define a recursive helper function
    def helper(n):
        # if n is not in memo, then calculate it
        if n not in memo:
            memo[n] = helper(n-1) + helper(n-2)
        # return the value of n from memo
        return memo[n]
    
    return helper(n)

# test
print(fibonacci(1))
print(fibonacci(2))
# this now is super fast
print(fibonacci(40))   

1
1
102334155

Another method is using dynamic programming (DP) table. The idea is same as the memo.

DP Table calculates f(n) from bottom to top, or from the smallest subproblem to the originam subproblem. For example, to calculate f(20), DP calculates f(1), f(2), ..., f(20) in sequence.

def fibonacci(n):
    # intialize a dp table
    dp = {i: 0 for i in range(1, n+1)}
    dp[1] = 1
    dp[2] = 1

    # solve subproblem from small to large
    for i in range(3, n+1):
        dp[i] = dp[i-1] + dp[i-2]
    
    return dp[n]

# test
print(fibonacci(1))
print(fibonacci(2))
# this now is super fast
print(fibonacci(40))

1
1
102334155

we can keep optimize the above method as only two values in the table are used at a time. There is no need to store all of them.

def fibonacci(n):
    dp_1 = 1
    dp_2 = 1

    for i in range(3, n+1):
        dp_1, dp_2 = dp_1 + dp_2, dp_1
    
    return dp_1

# test
print(fibonacci(1))
print(fibonacci(2))
# this now is super fast
print(fibonacci(40))

1
1
102334155

Coin Change#

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

Example 1:

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

This could be treated as a DP problem, as each subproblem is independent.

Naive Recursion#

We can construct a recusion by recursively reducing the amount by the available coin in coins, which leads to a new amount as a subproblem.

For a DP problem, we need:

  • base case: amount is 0, and if it’s negative then the amount cannot be made up by any combinations of the coins.

  • state, what will be changed in the origninal problem and its subproblem: in this case, it is the amount

  • choice, what are choices that lead to the state changes: the selection of coins

  • DP function/table definition:

    • from top-to-down recursion, we will use a DP function, which typically takes the state as an argument, and return what is required, such as the number of coins.

    • from bottom-to-up, we will use a DP table, which serves as a memo to avoid duplicated calculations.

The state change function can be:

(8)#\[\begin{align} f(x) = \begin{cases} 1 && x = 0 \\ -1 && x \lt 0 \\ \min \{f(x - c) + 1| c \in coins\} && x > 0 \end{cases} \end{align}\]
def coinChange(coins, amount):

    # dp function: get the minimum number of coins to make up amount
    def dp(amount):
        # if amount is 0, then return 0
        if amount == 0:
            return 0
        # if amount is negative, then return -1
        if amount < 0:
            return -1
        
        min_coins = float('inf')
        for coin in coins:
            # subproblem: get the minimum number of coins to make up amount - coin
            subproblem = dp(amount - coin)
            # if subproblem is unsolvable (-1), then skip it
            if subproblem == -1:
                continue
            # if subproblem is not -1, then update min_coins
            min_coins = min(min_coins, subproblem + 1) 
        
        return min_coins
    
    res = dp(amount)
    return res if res != float('inf') else -1

# test
# 3
print(coinChange([1,2,5], 11))
# -1
print(coinChange([2], 3))
# 0
print(coinChange([1], 0))
# this test will take a long time
# 6
print(coinChange([1,2,5], 30))

3
-1
0

6

Memoization#

Apparently, the above recursion has duplicated subproblems. We can use a memo to avoid duplicated calculations.

def coinChange(coins, amount):
    # initialize a memo to store the minimum number of coins to make up amount
    memo = {}

    # dp function: get the minimum number of coins to make up amount
    def dp(amount):
        # base cases
        if amount == 0:
            return 0
        if amount < 0:
            return -1

        # 
        min_amount = float('inf')
        # solve subproblems
        for coin in coins:
            # if amount - coin is not in memo, then calculate it and save it in memo
            if amount - coin not in memo:
                subproblem = dp(amount - coin)
                memo[amount-coin] = subproblem
            # if subproblem is unsolvable (-1), then skip it
            if memo[amount-coin] == -1:
                continue

            # update min_amount - state transition
            min_amount = min(min_amount, memo[amount-coin] + 1)

        # return the min_coins that can make up amount   
        memo[amount] = min_amount

        return memo[amount]

    res = dp(amount)
    return res if res != float('inf') else -1 

# test
# 3
print(coinChange([1,2,5], 11))
# -1
print(coinChange([2], 3))
# 0
print(coinChange([1], 0))     
# 20
print(coinChange([1,2,5], 100))

3
-1
0
20

DP Tables#

We can use DP table to avoid duplicated calculations. The idea is same as the memo.

def coinChange(coins, amount):
    dp = {i: float('inf') for i in range(1, amount+1)}
    dp[0] = 0

    for i in range(1, amount+1):
        for coin in coins:
            if i - coin < 0:
                continue
            dp[i] = min(dp[i], dp[i-coin] + 1)
    
    return dp[amount] if dp[amount] != float('inf') else -1

# test
# 3
print(coinChange([1,2,5], 11))
# -1
print(coinChange([2], 3))
# 0
print(coinChange([1], 0))
# 20
print(coinChange([1,2,5], 100))

3
-1
0
20

Longest Increasing Subsequence#

Find the longest increasing subsequence in a given sequence. For example, for nums = [10, 9, 2, 5, 3, 7, 101, 18], the output is 4 because the longest subsequence is [2, 3, 7, 101].

DP Table#

we divide the problem as:

  • for i in range(n):

    • dp[i] is the number of the longest subsequence in nums[i:]

    • to calculate dp[0], we need dp[1], ...., dp[n-1].

    • state transition: dp[i] = dp[i+1] if nums[i] >= min(nums[i+1:] else dp[i+1] + 1

  • base case: when i = n - 1, dp[i] = 1

  • choice: the choice that lead to subproblem for this problem is pretty simple by moving the pointer i forward

  • state: the length of the longest subsequence

  • state transition:

    • if nums[i] < min(num[i+1:])

      • dp[i] = dp[i+1] + 1

    • else:

      • dp[i] = dp[i+1]

This solution is not correct:

nums = [1, 4, 3, 4, 2] -> dp = [2, 1, 1, 1, 1] but the actual dp = [3, 2, 2, 1, 1].

Revisions

  • for i in range(n):

    • dp[i] is the number of the longest subsequence in nums[:i+1], which also ends with nums[i]

    • to calculate dp[i], we need dp[i-1], ..., dp[0]

    • state transition dp[i] = max(dp[j] + 1 for j in J such that nums[J] < nums[i])

  • base case: dp[0] = 1

  • choice: the choice that lead to subproblem for this problem is pretty simple by moving the pointer i forward

  • state: dp[i] is the length of the longest subsequence that ends with nums[i]

  • state transition:

    • for j in J such that nums[J] < nums[i] and J < i:

      • dp[i] = max(dp[i], dp[j]+1))

*========================

Note

  • the time complexity is \(O(n^2)\)

def longestIncreasingSubsequence(nums):
    if not nums:
        return 0

    # initialize a dp table
    dp = [1 for i in range(len(nums))]

    # solve subproblem from small to large
    for i in range(1, len(nums)):
        # find index j that nums[j] < nums[i]
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j]+1)
    # return the max value in dp table
    return max(dp)

# test
# 4
print(longestIncreasingSubsequence([10,9,2,5,3,7,101,18]))
# 1
print(longestIncreasingSubsequence([7,7,7,7,7,7,7]))
# 0
print(longestIncreasingSubsequence([]))

4
1
0

Russian Doll Envelopes#

Leetcode 0354

  • sort ascendingly the envelope by width

  • solve a longest subsequence problem

DP Function#

DP Function with Memo#

DP Table#

def dollEnvelopes(envelopes):
    if not envelopes:
        return 0

    # sort the envelopes by width and height
    envelopes.sort(key=lambda x: (x[0], x[1]))

    # initialize a dp table that stores the max number of dolls that can be put into the ith envelope
    dp = [1 for i in range(len(envelopes))]

    # solve subproblem from small to large
    for i in range(1, len(envelopes)):
        # find index j that envelopes[j] < envelopes[i]
        for j in range(i):
            if envelopes[j][0] < envelopes[i][0] and envelopes[j][1] < envelopes[i][1]:
                dp[i] = max(dp[i], dp[j]+1)
    # return the max value in dp table
    return max(dp)

# test
# 3
print(dollEnvelopes([[5,4],[6,4],[6,7],[2,3]]))

3

Edit Distance#

See Leetcode 0072

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.

You have the following three operations permitted on a word:

  • Insert a character

  • Delete a character

  • Replace a character

Example 1:

Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation: 
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')

Why is this a DP problem?

  • for two words, we usually need two pointers

  • finding the minimum edit distance between word1[:i+1] and word2[:j+1] can be converted to find the minimum edit distance between word1[:i] and word[:j]

    • e(i+1, j+1) = e(i, j) + de

    • de: the edit distance to make word1[i+1] and word2[j+1] the same

      • de = 1 if word1[i+1] != word2[j]

        • insert

        • replace

        • delete

      • de = 0 if word1[i+1] = word2[j]

operate from end to the start

  • base: pointer i or pointer j is done traversing, insert/delete the rest characters

    • if i < 0: i is done, and insert the untraversed charecters in word2 indexing from 0 to j to word1

    • if j < 0: j is done, delete the unvisited characters in word1

  • choice: different choices lead to different subproblems

    • insert

    • delete

    • replace

    • skip

  • state: the minimum number of edits based on current choice

  • state transition:

DP Function#

# DP function
def minDistance(word1, word2):

    # dp function: get the minimum number of operations to convert word1[:i] to word2[:j]
    def dp(i, j):
        # base cases
        if i == -1:
            return j+1
        if j == -1:
            return i+1
        
        # if the last characters of word1 and word2 are the same, then no operation is needed -> choose "skip"
        if word1[i] == word2[j]:
            return dp(i-1, j-1)
        # if the last characters of word1 and word2 are different, then we need to do 1 operation -> choose "insert", "delete" or "replace"
        # how to choose the operation? -> choose the operation that has the minimum number of operations
        else:
            return min(dp(i, j-1) + 1, # insert
                       dp(i-1, j) + 1, # delete
                       dp(i-1, j-1) + 1) # replace
    
    return dp(len(word1)-1, len(word2)-1)
    
# test
# 3
print(minDistance("horse", "ros"))
# 5
print(minDistance("intention", "execution"))

3
5

DP Function with Memo#

Add a memo to avoid duplicated subproblems.

# DP function
def minDistance(word1, word2):
    # initialize a memo to store the minimum number of operations to convert word1[:i] to word2[:j]
    memo = {}

    # dp function: get the minimum number of operations to convert word1[:i] to word2[:j]
    def dp(i, j):
        # base cases
        if i == -1:
            return j+1
        if j == -1:
            return i+1
        # if the subproblem is already solved, then return the result from memo    
        if (i, j) in memo:
            return memo[(i, j)]

        # save to memo if not solved
        # if the last characters of word1 and word2 are the same, then no operation is needed -> choose "skip"
        if word1[i] == word2[j]:
            memo[(i, j)] = dp(i-1, j-1)
        # if the last characters of word1 and word2 are different, then we need to do 1 operation -> choose "insert", "delete" or "replace"
        # how to choose the operation? -> choose the operation that has the minimum number of operations
        else:
            memo[(i, j)] = min(dp(i, j-1) + 1, # insert
                       dp(i-1, j) + 1, # delete
                       dp(i-1, j-1) + 1) # replace
        
        return memo[(i, j)]

    return dp(len(word1)-1, len(word2)-1)
    
# test
# 3
print(minDistance("horse", "ros"))
# 5
print(minDistance("intention", "execution"))
# 10
print(minDistance("zoologicoarchaeologist", "zoogeologist"))

3
5
10

DP Table#

Recursive solution with DP table.

In DP function, the base case is i, j = -1. But for a table, dp has to start from index i, j = 0, therefore, dp[0][0] will represent the value dp(-1, -1). Thus dp[i][j] should be be the same as dp(i-1, j-1), which stores the minimum edit distance between word1[:i] and word2[:j].

def minDistance(word1, word2):
    # define a dp table: dp[i][j] represents the minimum number of operations to convert word1[:i] to word2[:j]
    m, n = len(word1), len(word2)
    dp = [[0 for j in range(n+1)] for i in range(m+1)]
    
    for i in range(m+1):
        for j in range(n+1):
            # base cases
            if i == 0:
                dp[i][j] = j
            elif j == 0:
                dp[i][j] = i
            # normal cases 
            else:
                # if the last characters of word1 and word2 are the same, then no operation is needed -> choose "skip"
                if word1[i-1] == word2[j-1]:
                    dp[i][j] = dp[i-1][j-1]
                # if the last characters of word1 and word2 are different, then we need to do 1 operation -> choose "insert", "delete" or "replace"
                else:
                    dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])+1
    
    return dp[m][n]

# test
# 3
print(minDistance("horse", "ros"))
# 5
print(minDistance("intention", "execution"))
# 10
print(minDistance("zoologicoarchaeologist", "zoogeologist"))

3
5
10

Think about how to perform the edit?

In the above, we only know the minimum steps we need to perform, but what choices are used for each step and the order are not saved.

Longest Common Subsequence#

Leetcode

  • 1143

  • 0583

  • 0712

  • 2207

  • 1092

Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.

Example 1:

Input: text1 = "abcde", text2 = "ace" 
Output: 3  
Explanation: The longest common subsequence is "ace" and its length is 3.

DP Function#

def longestCommonSubsequence(text1, text2):
    m, n = len(text1), len(text2)

    # define a dp function
    def dp(i, j):
        # base cases
        if i == -1 or j == -1:
            return 0
        
        # if the last characters of text1 and text2 are the same, then we can add 1 to the result of dp(i-1, j-1)
        if text1[i] == text2[j]:
            return dp(i-1, j-1) + 1
        # if the last characters of text1 and text2 are different, then we need to choose the maximum result of dp(i-1, j) and dp(i, j-1)
        else:
            return max(dp(i-1, j), dp(i, j-1))

    return dp(m-1, n-1)

# test
# 3
print(longestCommonSubsequence("abcde", "ace"))

# 3
print(longestCommonSubsequence("abc", "abc"))

# 0
print(longestCommonSubsequence("abc", "def"))

3
3
0

DP Function with Memo#

def longestCommonSubsequence(text1, text2):
    memo = {}

    # dp function returns the longest common subsequence of text1[:i+1] and text2[:j+1]
    def dp(i, j):
        if i == -1 or j == -1:
            memo[(i,j)] = 0
        
        if (i,j) in memo:
            return memo[(i,j)]
        
        if text1[i] == text2[j]:
            memo[(i,j)] = dp(i-1, j-1) + 1
        else:
            memo[(i,j)] = max(dp(i-1, j), dp(i, j-1))

        return memo[(i,j)]

    return dp(len(text1)-1, len(text2)-1)
    
# test
# 3
print(longestCommonSubsequence("abcde", "ace"))

# 3
print(longestCommonSubsequence("abc", "abc"))

# 0
print(longestCommonSubsequence("abc", "def"))

3
3
0

DP Table#

DP table has a size of (m+1, n+1).

Therefore, dp[i][j] stores the longest common subsequences for text1[:i] and text2[:j]

def longestCommonSubsequence(text1, text2):
    # initialize a dp table that stores the longest common subsequence of text1[:i] and text2[:j]
    m, n = len(text1), len(text2)
    dp = [[0 for j in range(n+1)] for i in range(m+1)]

    for i in range(m+1):
        for j in range(n+1):
            if i == 0 or j == 0:
                dp[i][j] = 0
            elif text1[i-1] == text2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[m][n]

# test
# 3
print(longestCommonSubsequence("abcde", "ace"))

# 3
print(longestCommonSubsequence("abc", "abc"))

# 0
print(longestCommonSubsequence("abc", "def"))
    
    

3
3
0

0-1 N-Pack Problem#

Assume we have N items and a bag that can only hold W weight of items. vi = [v0, v1, ...] and wi = [w0, w1, ...] are the value and weight for each item. Output the maximum value of the items that can be put into the bag.

Leetcode

  • https://www.acwing.com/problem/content/2/

  • 0416

  • 0494

  • 0474

  • 1049

Analysis This is actaully a integer linear programming problem, which can be solved using dynamic programming if the problem is simple.

DP problem: the maximum value of the bag for storing the first i items is related to a subproblem, which is the maximum value of the bag for storing the first i-1 items.

  • state input: weights of the bag, and the selectable items

  • state: maximum value for current state inputs

  • base case: weight is 0 and no selectable items

  • choices: put item i in the bag or not

  • state transition:

    • if we cannot put item i in the bag: -> wi > w

      • dp[i][w] = dp[i-1][w] -> the bag with weight w has been filled already with the 0,.., i-1 items, therefore,

    • else we can:

      • dp[i][w] = max of the choices

        • do not put: dp[i][w] = dp[i-1][w]

        • put: dp[i-1, j]-wv[i][0]) + wv[i][1] -> put item i into bag so that the weight makes up to the desired weight

DP Function#

def maxValue(wv, W):
    # define a dp function that returns the maximum value of the items that can be put into a knapsack of capacity W
    def dp(i, j):
        # base cases
        if i == -1 or j == 0:
            return 0
        # if the weight of the i-th item is greater than the capacity of the knapsack, then we cannot put the i-th item into the knapsack
        if wv[i][0] > j:
            return dp(i-1, j)
        # if the weight of the i-th item is less than or equal to the capacity of the knapsack, then we can put the i-th item into the knapsack
        else:
            return max(dp(i-1, j), # do not put i-th item into the knapsack
                    dp(i-1, j-wv[i][0]) + wv[i][1]) # put i-th item into the knapsack
    
    return dp(len(wv)-1, W)

# test
# 22
print(maxValue([[1, 6], [2, 10], [3, 12]], 5))

# 16
print(maxValue([[1, 6], [2, 10], [3, 12]], 3))

# 6
print(maxValue([[2, 4], [1 ,2], [3, 3]], 4))

22
16
6

# this solution is wrong, because it does not consider the case where the weight of the i-th item is greater than the capacity of the knapsack
def maxValue(wv, W):
    # define a dp function that returns the maximum value of the items that can be put into a knapsack of capacity W
    def dp(i, j):
        # base cases
        if i == -1 or j == 0:
            return 0
        # if we can put item i into the knapsack, then we can choose to put it or not
        if wv[i][0] <= 1:
            return dp(i-1, j-1) + wv[i][1]
        # if we cannot put item i into the knapsack, then we have to skip it
        else:
            return max(dp(i-1, j), dp(i, j-1))

    return dp(len(wv)-1, W)

# test
# 22
print(maxValue([[1, 6], [2, 10], [3, 12]], 5))

# 12
print(maxValue([[1, 6], [2, 10], [3, 12]], 3))

6
6

DF Function with Memo#

def maxValue(wv, W):
    # initialize a memo
    memo = {}
    # define a dp function that returns the maximum value of 0th-ith items that can be put into a knapsack of capacity w
    def dp(i, w):
        # base cases
        if i == -1 or w == 0:
            memo[(i,w)] = 0
        
        # if we have already computed the result of dp(i, w), then we can directly return it
        if (i, w) in memo:
            return memo[(i, w)]
        
        # else we need to compute the result of dp(i, w)
        # if the we cannot put the ith item into the knapsack, then we have to skip it
        if wv[i][0] > w:
            memo[(i,w)] = dp(i-1, w)
        # if we can put the ith item into the knapsack, then we can choose to put it or not
        else:
            memo[(i, w)] = max(
                dp(i-1, w), # do not put the ith item into the knapsack
                dp(i-1, w-wv[i][0]) + wv[i][1] # put the ith item into the knapsack
            )
        return memo[(i, w)]

    return dp(len(wv)-1, W)

# test
# 22
print(maxValue([[1, 6], [2, 10], [3, 12]], 5))

# 16
print(maxValue([[1, 6], [2, 10], [3, 12]], 3))

# 6
print(maxValue([[2, 4], [1 ,2], [3, 3]], 4))

22
16
6

DP Table#

def maxValue(wv, W):
    # define a dp table so that dp[i][w] stores the maximum value of the first i items that can be put into a knapsack of capacity w
    n = len(wv) # number of items

    # initialize the dp table
    dp = [[0 for w in range(W+1)] for i in range(n+1)]

    # fill the dp table
    for i in range(n+1):
        for w in range(W+1):
            # base case: no items or capacity is 0: this is not necessary here as already defined during initialization
            # keep it here for completeness.
            if i == 0 or w == 0:
                 dp[i][w] = 0
            
            # if we cannot put item i into pack
            if wv[i-1][0] > w:
                dp[i][w] = dp[i-1][w]
            # else we can put item i into pack, but we want to the maximum value from 1) put and 2) not put
            else:
                dp[i][w] = max(wv[i-1][1] + dp[i-1][w-wv[i-1][0]],
                                dp[i-1][w])
    return dp[n][W]

# test
# 22
print(maxValue([[1, 6], [2, 10], [3, 12]], 5))

# 16
print(maxValue([[1, 6], [2, 10], [3, 12]], 3))

# 6
print(maxValue([[2, 4], [1 ,2], [3, 3]], 4))

22
16
6

DP Table with Space Optimization#

The above DP table has a size of (n+1, W+1). But during the state transition for [i][w], only [i-1][w] and [i-1][w-wv[i-1][0]] is needed. Therefore, there is no need to save other values.

**We can simply use a 1-D dp table to replace the 2-D table.

Note: the traverse order along W axis has to be from the end to beginning

1.先看原来2D情况，dp[i][j]的值，都是仅依靠上一行dp[i-1][…]得出的。意思是我们要算当前dp[i]行的值，仅需要上一行dp[i-1]就好。所以可以将其转化为：原地更新1D数组问题；

2.现在考虑降为1D，定义该1D数组为int[] dp。回忆原来2D情况，dp[i][j]的值都是依靠“其正上方的值dp[i-1][j]+左上方的值dp[i-1][j-nums[i]]”来更新。那么如果对1D进行正向遍历即从dp[0]->dp[n-1]填充，对于某一位例如dp[cur]的更新，势必会用到dp[pre]（pre<cur），因为是正向遍历，那么dp[pre]在当前轮次已经被更新过了，当在这种情况下计算的dp[cur]肯定不正确（其实说白了，就相当于2D情况下，使用了同一行的值。例如使用dp[i][j-nums[i]]来更新dp[i][j]）；

3.现在解释对1D数组进行反向遍历即从dp[n-1]->dp[0]填充。同样，对于某一位例如dp[cur]的更新，势必会用到dp[pre]（pre<cur）。但注意，因为是从后往前进行遍历的，此时dp[pre]在当前轮次未被更新，所以就相当于2D情况下使用的上一行的值，这样计算就是正确的了。

def maxValue(wv, W):
    n = len(wv)
    # initialize a dp 1-D array
    dp = [0 for i in range(W+1)]

    # fill the dp table
    for i in range(n):
        # we have to use the inverse order here
        for w in range(W, 0, -1):
            # if we cannot put item i into the bag 
            if wv[i][0] > w:
                dp[w] = dp[w]
            else:
                dp[w] = max(dp[w], wv[i][1] + dp[w - wv[i][0]])
    return dp[W]
# test
# 22
print(maxValue([[1, 6], [2, 10], [3, 12]], 5))

# 16
print(maxValue([[1, 6], [2, 10], [3, 12]], 3))

# 6
print(maxValue([[2, 4], [1 ,2], [3, 3]], 4))

22
16
6

Or we can use two 1-D array to store the maximum value for traversing the i-1 row.

def maxValue(wv, W):
    n = len(wv)
    # initialize a 1-D dp table for storing the max value when traversing row `i`
    dp = [0 for i in range(W+1)]

    # fill the 1-D dp table
    for i in range(n):
        dp_prev = dp[:]
        for w in range(W+1):
            # if we cannot put item i into pack
            if wv[i][0] > w:
                dp[w] = dp_prev[w]
            else:
                dp[w] = max(dp_prev[w],
                                wv[i][1] + dp_prev[w - wv[i][0]])
    return dp[W]

# test
# 22
print(maxValue([[1, 6], [2, 10], [3, 12]], 5))

# 16
print(maxValue([[1, 6], [2, 10], [3, 12]], 3))

# 6
print(maxValue([[2, 4], [1 ,2], [3, 3]], 4))         

22
16
6

Complete Pack#

Instead of outputing the minimum number of items that can be put into a bag with a capacity of W but gives the largest values, the other questions are:

  • can we put the items into the bag to make a target weight of W extactly?

  • if so, how many ways in total there will be?

A similar Leetcode is Coin Change II, where given a target amount=5 and coins=[1,2,5] with infinite number of each coin, how many ways there are to make up the target amount using these coins.

Leetcode

  • 0518

  • 0115

Analysis This is a complete pack problem, which needs to know all the possibile combinations of coins. Strictly speaking, this is not a dynamic programming problem as no optimality is requested, but this follows the subproblem structure with duplications, which could be solved using dynamic programming.

DP Function#

def change(amount, coins):

    # dp function dp(i,j) returns the total number of ways to make up a target j from the the 1th-ith coin.
    def dp(i, j):
        # base case
        # if no coins, we cannot make up any number
        if i == 0 and j != 0:
            return 0
        # if we need make up of number of 0, there is always one way, that is do not choose any coin
        if j == 0:
            return 1
        
        # cannot use ith coin
        if coins[i-1] > j:
            return dp(i-1, j)
        
        else:
            return dp(i-1, j) + dp(i, j-coins[i-1])
        
    return dp(len(coins), amount)

# test
# 4
amount = 5
coins = [1,2,5]
print(change(amount, coins))

# 0
amount = 5
coins = [3]
print(change(amount, coins))

4
0

DP Function with Memo#

def change(amount, coins):
    # initialize a memo
    memo = {}

    # define a dp function to return the total number of ways to make up a target j from the the 1th-ith coin.
    def dp(i, j):
        # if in memo, return
        if (i, j) in memo:
            return memo[(i, j)]
        # base case
        if i == 0 and j != 0:
            return 0
        if j == 0:
            return 1
        
        # if not in memo, then use dp to calculate memo
        if coins[i-1] > j:
            memo[(i, j)] = dp(i-1, j)
        else:
            memo[(i, j)] = dp(i-1, j) + dp(i, j-coins[i-1])
        
        return memo[(i, j)]
    
    return dp(len(coins), amount)

# test
# 4
amount = 5
coins = [1,2,5]
print(change(amount, coins))

# 0
amount = 5
coins = [3]
print(change(amount, coins))
    

4
0

DP Table#

Note: we can simply optimize the dp table space use by compress the 2-D table to 1-D.

def change(amount, coins):
    # number of choices
    n = len(coins)
    # initialize a dp table
    # dp[i][j] stores the number of ways to make up the target j with the first i coins
    dp = [[0 for j in range(amount+1)]]*(n+1)
    for i in range(n+1):
        # base case: without any coin, no target amount > 0 can be made; amount 0 can be made up without chosing any coins
        dp[i][0] = 1
    # state transition
    for i in range(1, n+1):
        for j in range(1, amount+1):
            # 0-index: if the (i-1)th coin is not able to be put into the bag, the skip
            if coins[i-1] > j:
                dp[i][j] = dp[i-1][j]
            # else: return the sum of 1) number of ways to make up target if we use coins[i-1] and 2) the number of ways to make up the target if we dont use coins[i-1]
            else:
                dp[i][j] = dp[i][j-coins[i-1]] + dp[i-1][j]
    return dp[n][amount]

# test
# 4
amount = 5
coins = [1,2,5]
print(change(amount, coins))

# 0
amount = 5
coins = [3]
print(change(amount, coins))

4
0
Contents