Categorygithub.com/szhou12/leetcode-goleetcode0474-Ones-and-Zeroes
package
0.0.0-20241220224003-b7cf03a90b2b
Repository: https://github.com/szhou12/leetcode-go.git
Documentation: pkg.go.dev
Overview
Dependencies
1
Dependents
0

# README

474. Ones and Zeroes

Solution idea

DP - 2维 0/1 Knapsack

  • 典型的 0/1 背包的题型. 在两个维度上分别做 1维 0/1 Knapsack

  • 在 n 个String中选出一些String，尽量完全填满 m 维和 n 维 这两个背包

Definition:

dp[i][j]: 最多有i个0和j个1的背包装下的String总数

Base Case:

01背包的dp数组初始化为0就可以。

因为物品价值不会是负数，初始为0，保证递推的时候dp[i][j]不会被初始值覆盖 (因为是用 max())。

Recurrence

dp[i][j] = max(dp[i][j], dp[i-zeros][j-ones] + 1)
  • 注意！！！遍历背包容量要从后向前遍历！这是为了防止double counting.

举一个例子：物品0的重量weight[0] = 1，价值value[0] = 15

如果正序遍历

dp[1] = dp[1 - weight[0]] + value[0] = 15

dp[2] = dp[2 - weight[0]] + value[0]
      = dp[2-1] + value[0] 
      = dp[1] + value[0] 
      = (dp[1 - weight[0]] + value[0]) + value[0]

dp[1] 就计算了添加物品0的情况.

此时dp[2]在考虑dp[1]时，意味着物品0，又被放入了一次，所以不能正序遍历。

倒序就是先算dp[2], 也就是说, 等会儿算dp[1] 时, dp[1]并不会考虑dp[2]的情况.

所以从后往前循环，每次取得状态不会和之前取得状态重合，这样每种物品就只取一次了.

Time complexity = $O(n * M * N)$ where $n=$ # of strings, $M, N$ 是两个维度上的背包最大容量

Resource