Solution to LeetCode 474 Ones and Zeros and LeetCode 494 Target Sum
LeetCode 474
Ones and Zeros (medium) [link]
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 0 and j 1. We iterate through all elements in the set. If we want to account for the next element with p 0 and q 1. 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 494
Target Sum (Medium) [link]
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[5] 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]
Template of 0-1 Knapsack Problem
0-1 knapsack problem:
- 2-d dp array:
- Outer for loop is iterating items, inner for loop is iterating capacities of knapsack. They CAN switch the position.
- 1-d dp array:
- Outer for loop is iterating items, inner for loop is iterating capacities of knapsack. They CANNOT switch the position.
Using 2-d dp array:
def test_0x_knapsack(bag_size, weight, value) -> int:
rows, cols = len(weight), bag_size + 1
dp = [[0 for _ in range(cols)] for _ in range(rows)]
# initialization
for i in range(rows):
dp[i][0] = 0
first_item_weight, first_item_value = weight[0], value[0]
for j in range(1, cols):
if first_item_weight <= j:
dp[0][j] = first_item_value
# loop items before iterating capacities
for i in range(1, len(weight)):
cur_weight, cur_val = weight[i], value[i]
for j in range(1, cols):
if cur_weight > j: # item is heavier than the capacity
dp[i][j] = dp[i - 1][j]
else:
# recurrence relation
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - cur_weight] + cur_val)
dp[rows-1][cols-1]
Using 1-d dp array (rolling array):
def test_01_knapsack():
weight = [1, 3, 4]
value = [15, 20, 30]
bag_weight = 4
dp = [0] * (bag_weight + 1)
# iterating items before iterating capacities
for i in range(len(weight)):
for j in range(bag_weight, weight[i] - 1, -1):
# recurrence relation
dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
print(dp)
