Article catalog
preface
Follow labuladong to brush the questions and make some notes. The original website link is: link.
1. Classical dynamic programming: 0-1 knapsack problem
Give you a backpack with a weight of W and N items. Each item has two attributes: weight and value. The weight of the ith item is wt[i] and the value is val[i]. Now, what is the maximum value you can pack with this back package?
Step 1: define [status] and [selection]
States are used to describe subproblems
For example, in this example, the state consists of two parts, the remaining capacity of the backpack and the items that can be selected
Selection is the connection between subproblems
For example, in this example, the choice is to pack an item into the backpack or not
for Status 1 in All values of status 1:
for Status 2 in All values of status 2:
for ...
dp[Status 1][Status 2][...] = preferential(Select 1, select 2...)
Step 2: define the dp array
First, look at the "states" just found. There are two, that is, we need a two-dimensional dp array.
dp[i][w] is defined as follows: for the first I items, the capacity of the current backpack is w
In this case, the maximum value that can be installed is dp[i][w].
For example, if dp[3][5] = 6, it means that for a given series of items, if only the first three items are selected, when the backpack capacity is 5, the maximum value that can be loaded is 6.
base case is dp[0] [...] = dp [...] [0] = 0, because when there is no item or backpack has no space, the maximum value that can be loaded is 0.
int[][] dp[N+1][W+1]
dp[0][..] = 0
dp[..][0] = 0
for i in [1..N]:
for w in [1..W]:
dp[i][w] = max(
Put the item i Put it in your backpack,
Don't put things i Put it in your backpack
)
return dp[N][W]
Step 3: think about the logic of state transition according to "choice".
How can "put item i into the backpack" and "don't put item i into the backpack" in the above pseudo code be reflected in the code?
We need to combine the definition of dp array to see how these two choices affect the state:
If you don't pack the ith item into your backpack, it is obvious that the maximum value dp[i][w] should be equal to dp[i-1][w], inheriting the previous results.
If you load the ith item into your backpack, dp[i][w] should be equal to dp[i-1][w - wt[i-1]] + val[i-1].
(details): since i starts from 1, when the indexes of val and wt are i-1, they represent the value and weight of the ith article.
Pseudo code:
for i in [1..N]:
for w in [1..W]:
dp[i][w] = max(
dp[i-1][w],
dp[i-1][w - wt[i-1]] + val[i-1]
)
return dp[N][W]
2. Classical dynamic programming: subset knapsack problem
416. Segmentation and subsets (medium)
Give you a non empty array num that contains only positive integers. Please judge whether this array can be divided into two subsets so that the sum of the elements in the two subsets is equal.
The problem can be transformed into a 0,1 knapsack problem
Use half of the sum of the nums array as the backpack capacity to see if you can use a subset to get this result
Status: remaining capacity, optional items
Choice: installed or not installed
dp[i][w] = ture means I items can be selected, and it can be filled exactly when the remaining w capacity is available
basecase: dp[0][...] = false dp[...][0] = true
class Solution:
def canPartition(self, nums: List[int]) -> bool:
s = sum(nums)
if s %2 != 0:
return False
weight = int(s/2)
n = len(nums)
dp = [[False] * (weight + 1) for _ in range(n + 1)]
#dp[n][weight]
#base case, when the remaining capacity is 0, it is full without loading
for i in range(n+1):
dp[i][0] = True
for i in range(1, n + 1):
for j in range(1, weight + 1):
if j >= nums[i-1]:
#Notice that both here are i-1
dp[i][j] = dp[i-1][j-nums[i-1]] or dp[i-1][j]
else:
dp[i][j] = dp[i-1][j] #Not big enough to fit the i-th one
return dp[n][weight]
State compression
class Solution:
def canPartition(self, nums: List[int]) -> bool:
s = sum(nums)
if s %2 != 0:
return False
weight = int(s/2)
n = len(nums)
dp = [False] * (weight + 1)
#dp[n][weight]
#base case, when the remaining capacity is 0, it is full without loading
dp[0] = True
for i in range(1, n + 1):
for j in reversed(range(1, weight + 1)):
if j >= nums[i-1]:
dp[j] = dp[j-nums[i-1]] or dp[j]
return dp[weight]
Note here for j in reversed(range(1, weight + 1)):
It is traversal from back to front, because dp[j-nums[i-1]] should actually be the data dp[i-1][j-nums[i-1]] of the previous line
Through traversal from back to front, dp[j-nums[i-1]] is not changed when dp[j] is calculated and changed, so dp[j-nums[i-1]] can still be used as the data of the previous line
3. Classical dynamic programming: complete knapsack problem
518. Change II (medium)
Give you an integer array. Coins represents coins of different denominations, and an integer amount represents the total amount.
Please calculate and return the number of coin combinations that can be rounded up to the total amount. If the total amount cannot be rounded up by any combination of coins, return 0.
Suppose there are an infinite number of coins of each denomination.
Input: amount = 5, coins = [1, 2, 5] Output: 4 Explanation: there are four ways to add up the total amount: 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1
We can transform this problem into a description of knapsack problem:
There is a backpack with a maximum capacity of amount and a series of items. The weight of each item is coins[i], and the number of each item is unlimited. How many ways can you fill your backpack exactly?
The complete knapsack problem is that the number of each item can be unlimited
Status: remaining capacity, optional items
Selection: how many are currently installed
dp array definition: dp[weight][i] = res indicates that the remaining capacity is weight. When the first I items can be selected, the total number of combinations
Initialization: dp[weight][i] is 0
basecase: dp[0] [...] = 1 means that when the weight is 0, there is exactly one combination no matter how you choose, that is, choose nothing
Choice: how many
Install 0 pieces: dp[weight][i] = dp[weight][i-1]
Install 1: dp[weight][i] = dp[weight - coins[i-1]][i-1]
Install 2: dp[weight][i] = dp[weight - 2 * coins[i-1]][i-1]
...
Until weight - 2 * coins [I-1] < 0
class Solution:
def change(self, amount: int, coins: List[int]) -> int:
n = len(coins)
weight = amount
dp = [[0] * (n+1) for _ in range(weight + 1)]
dp[0] = [1] * (n + 1)#basecase: when weight = 0
for w in range(1, weight + 1):
for i in range(1, n + 1):
k = 0
while w >= k * coins[i-1]:
dp[w][i] += dp[w - k * coins[i-1]][i-1]
k += 1
return dp[weight][n]
This method is very slow. The reason is that there is a while loop in our two loops, or many repeated subproblems are calculated
In fact, it can be improved a little
class Solution:
def change(self, amount: int, coins: List[int]) -> int:
n = len(coins)
weight = amount
dp = [[0] * (n+1) for _ in range(weight + 1)]
dp[0] = [1] * (n + 1)#basecase: when weight = 0
for w in range(1, weight + 1):
for i in range(1, n + 1):
if w >= coins[i-1]:
dp[w][i] = dp[w - coins[i-1]][i] + dp[w][i-1]
else:
dp[w][i] =dp[w][i-1]
return dp[weight][n]
I'm compressing the space
class Solution:
def change(self, amount: int, coins: List[int]) -> int:
n = len(coins)
weight = amount
dp = [0] * (weight + 1)
dp[0] = 1
for i in range(1, n + 1):
for w in range(1, weight + 1):
if w >= coins[i-1]:
dp[w] = dp[w - coins[i-1]] + dp[w]
return dp[weight]
Note here that the traversal order of i and w should be changed