474. 一和零
我的思路
题意分析
相当于给你一个数组 s t r s = [ ( a 0 , b 0 ) , ( a 1 , b 1 ) … ( a l − 1 , b l − 1 ) ] strs = [(a_0,b_0), (a_1, b_1) \ldots (a_{l-1}, b_{l-1})] strs=[(a0,b0),(a1,b1)…(al−1,bl−1)], a i a_i ai是 0 的个数， b i b_i bi是 1 的个数，数组长度为 l l l。
同时给你两个数字 ( m , n ) (m, n) (m,n)，求从 s t r s strs strs中选出来 k k k 组，使得 k k k 组的所有 a a a 相加小于等于 m m m，并且 b b b 相加小于等于 n n n，求最大的 k k k。
别的不会，先写个爆搜
我们定义 dfs(int index, int left_m, int left_n) 代表 当前 我们搜索到了数组的
i
n
d
e
x
index
index 号元素，同时剩余可以用的 0 和 1 的个数分别是 left_m 和 left_n。函数的返回结果是，根据上述条件，能够获得的最大的
k
k
k。
对于第 i n d e x index index 号元素：
- 我们可以不选，那么，继续搜索
dfs(index+1, left_m, left_n)。 - 只有当
a
i
n
d
e
x
≤
l
e
f
t
_
m
a
n
d
b
i
n
d
e
x
≤
l
e
f
t
_
n
a_{index} \le left\_m \quad and \quad b_{index} \le left\_n
aindex≤left_mandbindex≤left_n时，我们才能选择要 ：
dfs(index+1, left_m-a_index, left_n-b_index)。
因此，当前的返回值是选与不选两种情况的最大值。
当 i n d e x = s t r s . s i z e ( ) index = strs.size() index=strs.size() 时，返回 0 即可。
写出代码
class Solution {
public:
vector<pair<int, int>> cnt;
int LEN = 0;
int findMaxForm(vector<string>& strs, int m, int n) {
LEN = strs.size();
memset(f, -1, sizeof(f));
for (auto& str : strs){
int num_0 = 0, num_1 = 0;
for (auto ch : str){
if (ch == '0'){
num_0 ++;
}else if (ch == '1'){
num_1 ++;
}
}
cnt.emplace_back(pair<int, int>(num_0, num_1));
}
return dfs(0, m, n);
}
int dfs(int index, int left_m, int left_n){
if (index >= LEN){
return 0;
}
int a = dfs(index+1, left_m, left_n);
int b = 0;
if (left_m - cnt[index].first >= 0 && left_n - cnt[index].second >= 0){
b = dfs(index+1, left_m - cnt[index].first, left_n - cnt[index].second) + 1;
}
int ret = max(a, b);
return ret;
}
};
记忆化搜索
显然，写出来后，发现index，left_m， left_n三个变量在搜索中可能会出现重复，于是使用一个三维数组记录该三个变量。
记忆化搜索嘛，一般会AC(笑)。那这题一定也能用动态规划喽~
AC代码如下：
class Solution {
public:
vector<pair<int, int>> cnt;
int LEN = 0;
int f[602][102][102];
int findMaxForm(vector<string>& strs, int m, int n) {
LEN = strs.size();
memset(f, -1, sizeof(f));
for (auto& str : strs){ // 预处理
int num_0 = 0, num_1 = 0;
for (auto ch : str){
if (ch == '0'){
num_0 ++;
}else if (ch == '1'){
num_1 ++;
}
}
cnt.emplace_back(pair<int, int>(num_0, num_1));
}
return dfs(0, m, n);
}
int dfs(int index, int left_m, int left_n){
if (index >= LEN){
return 0;
}
if (f[index+1][left_m][left_n] != -1){ // 剪枝，如果数组中存在，那么直接返回
return f[index+1][left_m][left_n];
}
int a = dfs(index+1, left_m, left_n);
int b = 0;
if (left_m - cnt[index].first >= 0 && left_n - cnt[index].second >= 0){
b = dfs(index+1, left_m - cnt[index].first, left_n - cnt[index].second) + 1;
}
f[index+1][left_m][left_n] = max(a, b); // 记录在数组中
return f[index+1][left_m][left_n];
}
};
时间复杂度： O ( L E N ⋅ m ⋅ n + ∑ i = 0 L E N − 1 s i z e ( s t r s i ) ) O(LEN \cdot m \cdot n + \sum_{i=0}^{LEN-1}size(strs_i)) O(LEN⋅m⋅n+∑i=0LEN−1size(strsi))，显然，一种最坏的情况是：每一个位置都有 m 和 n 个剩余，那么dfs的时间复杂度是 O ( L E N ⋅ m ⋅ n ) O(LEN \cdot m \cdot n) O(LEN⋅m⋅n)，同时，预处理需要遍历 s t r s strs strs中的每一个字符，时间复杂度是 O ( ∑ i = 0 L E N − 1 s i z e ( s t r s i ) ) O(\sum_{i=0}^{LEN-1}size(strs_i)) O(∑i=0LEN−1size(strsi))
空间复杂度：
O
(
L
E
N
⋅
m
⋅
n
)
O(LEN \cdot m \cdot n)
O(LEN⋅m⋅n) , 一个 f 数组占用
O
(
L
E
N
⋅
m
⋅
n
)
O(LEN \cdot m \cdot n)
O(LEN⋅m⋅n), 一个cnt 占用
O
(
L
E
N
)
O(LEN)
O(LEN), 因此是
O
(
L
E
N
⋅
m
⋅
n
)
O(LEN \cdot m \cdot n)
O(LEN⋅m⋅n)。其实是
O
(
1
)
O(1)
O(1)，因为f大小固定(笑)。
动态规划
有了上述 记忆化搜索的经验，我们可以轻松地定义动态规划的数组，转义状态，以及初始条件。
数组定义
定义 f[i][j][k] 表示 数组的前
i
i
i个元素组成的新数组, 0 的可用个数是
j
j
j, 1 的可用个数是
k
k
k，能够获得的最大的个数。
显然，最终结果是 ： f[LEN][m][n]， LEN 是
s
t
r
s
strs
strs 的大小。
状态转移
我们记第 i i i 个元素的 0 的个数是 n u m 0 num_0 num0，1 的个数是 n u m 1 num_1 num1。
当第 i i i 号元素可以选择时，即 j ≥ n u m 0 & k ≥ n u m 1 j \ge num_0\ \And \ k \ge num_1 j≥num0 & k≥num1，此时 f [ i ] [ j ] [ k ] = m a x ( f [ i − 1 ] [ j ] [ k ] , f [ i − 1 ] [ j − n u m 0 ] [ k − n u m 1 ] + 1 ) f[i][j][k] = max(f[i-1][j][k], f[i-1][j-num_0][k-num_1] + 1) f[i][j][k]=max(f[i−1][j][k],f[i−1][j−num0][k−num1]+1)
当第 i i i 号元素无法选择时，即 j < n u m 0 ∣ k < n u m 1 j \lt num_0\ | \ k \lt num_1 j<num0 ∣ k<num1，此时 f [ i ] [ j ] [ k ] = f [ i − 1 ] [ j ] [ k ] f[i][j][k] = f[i-1][j][k] f[i][j][k]=f[i−1][j][k]
转移方程：
f
[
i
]
[
j
]
[
k
]
=
{
m
a
x
(
f
[
i
−
1
]
[
j
]
[
k
]
,
f
[
i
−
1
]
[
j
−
n
u
m
0
]
[
k
−
n
u
m
1
]
+
1
)
,
j
≥
n
u
m
0
&
k
≥
n
u
m
1
f
[
i
−
1
]
[
j
]
[
k
]
,
j
<
n
u
m
0
∣
k
<
n
u
m
1
f[i][j][k] = \begin{cases} max(f[i-1][j][k], f[i-1][j-num_0][k-num_1] + 1),&j \ge num_0\ \And \ k \ge num_1\\ f[i-1][j][k],&j \lt num_0\ | \ k \lt num_1 \end{cases}
f[i][j][k]={max(f[i−1][j][k],f[i−1][j−num0][k−num1]+1),f[i−1][j][k],j≥num0 & k≥num1j<num0 ∣ k<num1
初始条件
显然，当
i
=
0
i=0
i=0 时，新数组是空的，此时对于任何的 m 或 n, 都有 f[0][*][*] = 0。
写出代码
class Solution {
public:
int findMaxForm(vector<string>& strs, int m, int n) {
vector<pair<int, int>> cnt;
int LEN = strs.size();
for (auto& str : strs){ // 预处理
int num_0 = 0, num_1 = 0;
for (auto ch : str){
if (ch == '0'){
num_0 ++;
}else if (ch == '1'){
num_1 ++;
}
}
cnt.emplace_back(pair<int, int>(num_0, num_1));
}
int f[602][102][102] = {0};
for (int i = 1; i <= LEN; i ++){
for (int j = 0; j <= m; j ++){
for (int k = 0; k <= n; k ++){
if (cnt[i-1].first <= j && cnt[i-1].second <= k){
f[i][j][k] = max(f[i-1][j][k], f[i-1][j - cnt[i-1].first][k - cnt[i-1].second] + 1);
}else{
f[i][j][k] = f[i-1][j][k];
}
}
}
}
return f[LEN][m][n];
}
};
时间复杂度：
O
(
L
E
N
⋅
m
⋅
n
+
∑
i
=
0
L
E
N
−
1
s
i
z
e
(
s
t
r
s
i
)
)
O(LEN \cdot m \cdot n + \sum_{i=0}^{LEN-1}size(strs_i))
O(LEN⋅m⋅n+∑i=0LEN−1size(strsi))
空间复杂度：
O
(
L
E
N
⋅
m
⋅
n
)
O(LEN \cdot m \cdot n)
O(LEN⋅m⋅n)
优化空间复杂度
显然，我们可以将第一维度用 滚动数组的形式优化掉。
如果我们将第一维度去掉，代码会变成：
if (cnt[i-1].first <= j && cnt[i-1].second <= k){
f[j][k] = max(f[j][k], f[j - cnt[i-1].first][k - cnt[i-1].second] + 1);
}
显然，在计算f[k][j]时，需要保证f[j - cnt[i-1].first][k - cnt[i-1].second] + 1未被更新，因此内两层循环都需要倒序遍历。
class Solution {
public:
int findMaxForm(vector<string>& strs, int m, int n) {
vector<pair<int, int>> cnt;
int LEN = strs.size();
for (auto& str : strs){ // 预处理
int num_0 = 0, num_1 = 0;
for (auto ch : str){
if (ch == '0'){
num_0 ++;
}else if (ch == '1'){
num_1 ++;
}
}
cnt.emplace_back(pair<int, int>(num_0, num_1));
}
int f[102][102] = {0};
for (int i = 1; i <= LEN; i ++){
for (int j = m; j >= 0; j --){ // 倒序
for (int k = n; k >= 0; k --){ // 倒序
if (cnt[i-1].first <= j && cnt[i-1].second <= k){
f[j][k] = max(f[j][k], f[j - cnt[i-1].first][k - cnt[i-1].second] + 1);
}
}
}
}
return f[m][n];
}
};
时间复杂度：
O
(
L
E
N
⋅
m
⋅
n
+
∑
i
=
0
L
E
N
−
1
s
i
z
e
(
s
t
r
s
i
)
)
O(LEN \cdot m \cdot n + \sum_{i=0}^{LEN-1}size(strs_i))
O(LEN⋅m⋅n+∑i=0LEN−1size(strsi))
空间复杂度：
O
(
m
⋅
n
)
O(m \cdot n)
O(m⋅n)
2021.10.06 12:15
昨天把《Flask Web开发实战——入门、进阶与原理解析》，也就是李辉大神所著的“狼书”看完了一遍，虽然后面的Flask原理没咋看明白。
囫囵吞枣式地看了一遍，了解了很多工程方面的新知识，不能说学到了，只能说知晓了。
昨日，进行的工作还有：写了一篇博客；看Fluent Python一书第5章；做外包的活儿；做AML crawler的事情，可算完成了一小部分；洗了衣服和床上用品；等。
准备学习一下 vue ，貌似 在 jinja2 和 vue 之间我要做出抉择。
小孩子才做选择，成年人的世界就是：我都要（笑）。
身体力行，获得新知。