Summary of Dynamic Programming II. (Knapsack problems)
LeetCode 416 Partition Equal Subset Sum
We want to find a subset of numbers whose summation is equal to half of the total summation.
This problem can be seen as a 0-1 knapsack problem. The volume of knapsack is sum/2. The numbers can be seen as values or weights of items. If the knapsack can be taken up by some numbers, we are done. We assume items are not allowed to be repeatedly put into the knapsack.
Define dp[j] array as the maximal total value of items taken by a knapsack with j capacity.
The recurrence relation of 0-1 knapsack problem is dp[j] = max(dp[j], dp[j-w[i]]+v[i]). Since w[i] and v[i] are the same as num[i] in this problem, the recurrence relation is dp[j] = max(dp[j], dp[j-num[i]]+num[i]).
The base case is dp[0]=0 when the capacity is none. The dp array is initiated to have a size of 10001., because the values in an array <= 100 and the length of array is <= 200. So the total is <=20000, while the half is <=10000. Therefore, we can safely initialize dp=[0]*10001. If dp[j]==j, the answer to the question is yes.
The time complexity is O(n^2). The space complexity is O(n).
class Solution:
def canPartition(self, nums: List[int]) -> bool:
target = sum(nums)
if target % 2 == 1: return False
target //= 2
dp = [0]*10001
for i in range(len(nums)):
for j in range(target, nums[i]-1, -1):
dp[j] = max(dp[j], dp[j-nums[i]]+nums[i])
return target == dp[target]
Similar: LeetCode 698, LeetCode 473
LeetCode 1049 Last Stone Weight II
We can consider this problem as a 0-1 knapsack problem. The idea is to have two groups of stones with as same total weights as possible. In this case, after smashing them, the remaining stone has the smallest weight. The weight and the value are both stone[i].
Define dp[j] as the knapsack with capacity j. The recurrence relation for the 0-1 knapsack problem is dp[j] = max(dp[j], dp[j-w[i]] + v[i]). The recurrence relation for this problem is dp[j] = max(dp[j], dp[j-stone[i]] + stone[i]).
The base case is dp[0]=0 for zero capacity. Since 1 <= len(stones) <= 30，1 <= stones[i] <= 1000, the max weight is 30*1000=30000 . Therefore, the length of dp array can be safely initiated to be 15001.
class Solution:
def lastStoneWeightII(self, stones: List[int]) -> int:
total = sum(stones)
target = total // 2
dp = [0] * 150001
for i in range(len(stones)):
for j in range(target, stones[i] - 1, -1):
dp[j] = max(dp[j], dp[j-stones[i]]+stones[i])
return total - 2 * dp[target]
LeetCode 494 Target Sum
This problem can be seen as a 0-1 knapsack problem. We want to get the target. From left set - right set = target and left set + right set = sum, we get left = (target + sum)/2. The problem is to find the number of combination of left operations that equals to (target + sum)/2 . Any element can only be used once.
When there is no solution: 1) (target + sum)/2 is not an integer 2) the target is larger than the total sum.
Define dp[j] array as the number of ways to take up a knapsack with j capacity. The recurrence relation is dp[j]+=dp[j-nums[i]], meaning that for every possible i, the number of ways to get dp[j] should be accumulated.
The base case is dp[0]=1 because there is 1 way to take up a knapsack with zero capacity, that is to fill in nothing.
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
total = sum(nums)
left = (target + total) // 2
if abs(target) > total or (target + total) % 2 == 1:
return 0
dp = [0] * (left+1)
dp[0] = 1
for i in range(len(nums)):
for j in range(left, nums[i]-1, -1):
dp[j] += dp[j-nums[i]]
return dp[left]
LeetCode 474 Ones and Zeros
This problem can be seen as a 0-1 knapsack problem. A knapsack has two capacities: m and n.
Define dp[i][j] as the maximum size of subset with at most i 0s and j 1s. We iterate through all elements in the set. If we want to account for the next element with p 0s and q 1s. The size of the new subset can be obtained by dp[i][j] = dp[i-p][j-q] + 1. And we want the size of the subset to be the maximum, so dp[i][j] = max(dp[i][j],dp[i-p][j-q] + 1). Therefore, the recurrence relation is dp[i][j] = max(dp[i][j],dp[i-p][j-q] + 1).
The base case is dp[0][0]=0 meaning no / empty subset. The outer for loop is iterating the items. The inner for loop is iterating the capacity in reverse order. Note that there are two dimension of capacities, so we need two nested for loop in the outer loop.
class Solution:
def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
dp = [[0] * (n+1) for _ in range(m+1)]
for itm in strs:
onesNum = itm.count('1')
zerosNum = itm.count('0')
for i in range(m, zerosNum-1, -1):
for j in range(n, onesNum-1, -1):
dp[i][j] = max(dp[i][j], dp[i-zerosNum][j-onesNum] + 1)
return dp[m][n]
LeetCode 518 Coin Change II
Define dp[j] as the number of combination with a sum of j. The recurrence relation is dp[j] += dp[j-coins[i]]. The base case dp[0]=1 meaning there is only one combination that can have a sum of 0.
The outer for loop is iterating the values of coins, and the inner for loop is iterating the capacities.
class Solution:
def change(self, amount: int, coins: List[int]) -> int:
dp = [0] * (amount+1)
dp[0] = 1
for i in range(len(coins)):
for j in range(coins[i], amount+1): # if the knapsack can take it
dp[j] += dp[j-coins[i]]
return dp[amount]
LeetCode 377 Combination Sum IV
Note that different sequences are counted as different permutations. So the outer loop should iterate through capacities and the inner loop should iterate through items.
class Solution:
def combinationSum4(self, nums: List[int], target: int) -> int:
dp = [0] * (target+1)
dp[0]=1
for j in range(1, target+1):
for i in range(len(nums)):
if nums[i] <= j: # if the knapsack can take it
dp[j] += dp[j-nums[i]]
return dp[target]
LeetCode 70 Climbing Stairs
The question is asking the number of distinct ways to climb to the top. There are two ways to reach the top, one is by climbing one step, the other is by climbing two steps. So the number of distinct ways to reach the top is the sum of the number of distinct ways to reach the last step and the number of distinct ways to reach the second to last step.
Define dp[i] as the number of distinct ways to climb to the ith staircase. Since we can either climb 1 or 2 steps, there are two ways to climb to the ith staircase, either from dp[i-1] by one step or from dp[i-2] by two steps. Therefore we have dp[i] = dp[i - 1] + dp[i - 2]. From this formula we know that the iteration is going forward from the beginning. The base cases are dp[0]=dp[1]=1 meaning that there is only 1 way to go to the first stair or stay there.
1] Dynamic programming
class Solution:
def climbStairs(self, n: int) -> int:
dp=[0]*(n+1)
dp[0]=1
dp[1]=1
for i in range(2,n+1):
dp[i]=dp[i-1]+dp[i-2]
return dp[n]
class Solution(object):
def climbStairs(self, n):
a, b = 1, 1
for i in range(n):
a, b = b, a+b
return a
2] Complete knapsack problem
Define dp[i] as the number of distinct ways to reach the top. The recurrence relation is dp[j] += dp[i-j]. The base case dp[0]=1, other values are 0.
Note that we want the number of permutations of steps (rather than combinations), meaning that step 1->2 and step 2->1 are different. Therefore, the outer for loop should iterate capacities, and the inner for loop should iterate items.
The time complexity O(n^2). The space complexity is O(n).
class Solution:
def climbStairs(self, n: int) -> int:
dp = [0]*(n+1)
dp[0]=1
for j in range(n+1):
for i in range(1,2+1):
if j >= i:
dp[j] += dp[j-i]
return dp[n]
LeetCode 322 Coin Change
This is a 0-x Knapsack problem since we can have multiple copies of coins with the same value.
Define dp[j] as the minimum number of coins to have a sum of j. The recurrence relation is dp[j] = min(dp[j], dp[j-coins[i]] + 1). The base case is dp[0]=0, meaning we need 0 coins to sum to 0. Other values should be infinitely large.
In this problem, we don’t care about either we are counting permutations or combinations, so the outer loop can iterate items or capacities. The inner loop should be in the regular order (not reverse).
1] The inner loop iterates coins, and the outer loop iterates amount.
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
dp = [amount+1] * (amount+1)
dp[0] = 0
for i in range(len(coins)):
for j in range(coins[i], amount+1):
dp[j] = min(dp[j], dp[j-coins[i]]+1)
return dp[amount] if dp[amount] <= amount else -1
2] The outer loop iterates amount, and the inner loop iterates coins.
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
dp = [amount+1] * (amount+1)
dp[0] = 0
for j in range(1,amount+1):
for i in range(len(coins)):
if coins[i] <= j:
dp[j] = min(dp[j], dp[j-coins[i]]+1)
return dp[amount] if dp[amount] <= amount else -1
LeetCode 279 Perfect Squares
This is a 0-x knapsack problem.
Define dp[j] as the least number of perfect square numbers that sum to j. The recurrence relation is dp[j]= min(dp[j], dp[j-nums[i]]+1).
Since 1 <= n <= 10^4, the size of dp array should be 10^4.
class Solution:
def numSquares(self, n: int) -> int:
nums = [x * x for x in range(1,n+1) if x * x <= n]
dp = [10**4] * (n + 1)
dp[0] = 0
for i in range(len(nums)):
for j in range(nums[i], n+1):
dp[j] = min(dp[j], dp[j-nums[i]]+1)
return dp[n]
LeetCode 139 Word Break I
1] Dynamic Programming. tmp[i] = True means the first i characters of the string can be found in wordDict. tmp[-1] = True means the string can be segmented into words and these words can be found in wordDict.
Time complexity O(n^2), space complexity O(n), where n is the length of word s.
class Solution(object):
def wordBreak(self, s, wordDict):
n = len(s)
tmp = [False]*(n+1)
tmp[0] = True
for i in range(n):
for j in range(i+1, n+1):
if (tmp[i] and (s[i:j] in wordDict)):
tmp[j] = True
return tmp[-1]
Time complexity O(nm), space complexity O(n).
class Solution(object):
def wordBreak(self, s, wordDict):
n = len(s)
tmp = [False] * (n+1)
tmp[0] = True
for i in range(1, n+1):
for w in wordDict:
if i - len(w) >= 0 and (s[i-len(w):i] == w) and tmp[i-len(w)]:
tmp[i] = True
return tmp[-1]
# same
class Solution(object):
def wordBreak(self, s, wordDict):
n = len(s)
tmp = [False] * (n+1)
tmp[0] = True
for i in range(1, n+1):
for w in wordDict:
if tmp[i] or (s[i-len(w):i] == w) and tmp[i-len(w)]:
tmp[i] = True
return tmp[-1]
2] Complete Knapsack
Define dp[i] as (true/false) whether the string of length i can be segmented into the dictionary words. The main idea: for target in s, for word in wordDict, dp[i] = dp[i] or (dp[i-words] and words).
Time complexity O(nm), space complexity O(n).
class Solution(object):
def wordBreak(self, s, wordDict):
n = len(s)
dp = [False]*(n+1)
dp[0] = True
for i in range(1, len(s) + 1):
for word in wordDict:
dp[i] = dp[i] or (dp[i - len(word)] and s[i - len(word):i] == word)
# if dp[i] = True, then all dp[i] following it is True
return dp[-1]
