题目看上去很唬人,但是恰恰是这样说明该题设计的目的很强,指向dp的01背包,就是为了考01背包设计的。
10年积累的网站设计制作、做网站经验,可以快速应对客户对网站的新想法和需求。提供各种问题对应的解决方案。让选择我们的客户得到更好、更有力的网络服务。我虽然不认识你,你也不认识我。但先网站设计后付款的网站建设流程,更有鸡泽免费网站建设让你可以放心的选择与我们合作。像极了中学时代的那种看上去花里胡哨,实质上是根据考点设计出题的题目。(这种题看破出题意图,往往都很简单)
为什么说是考察01背包,代码随想录–474.一和零中描述的很清楚,不赘述。
这里直接给出转移方程:
f
(
k
,
i
,
j
)
=
f
(
k
−
1
,
i
,
j
)
+
(
k
−
1
,
i
−
[
k
]
,
j
−
[
k
]
)
f(k,i,j)=f(k-1,i,j)+(k-1,i-[k],j-[k])
f(k,i,j)=f(k−1,i,j)+(k−1,i−[k],j−[k])
其中:k表示候选元素的范围,(i,j)表示0与1的上限个数。
既然有了转移方程,那么该如何遍历呢?
就如同01背包一样,先循环k或者先循环i,j都是可以的,不过在力扣上先循环k的速度要快些,先循环i,j速度要比先k慢上不少;
这是先循环k的性能;
这是先循环i,j的性能;
k先循环的Java代码如下:
class Solution {public int findMaxForm(String[] strs, int m, int n) {int len = strs.length;
int[][][] f = new int[len+1][m+1][n+1];
for(int k = 1; k<= len; k++){//先循环k
String s = strs[k-1];
int[] set = getSet(s);
for(int i = 0; i<= m; i++){for(int j = 0; j<= n; j++){f[k][i][j] = f[k-1][i][j];
if(i-set[0] >= 0 && j-set[1] >= 0)
f[k][i][j] = Math.max(f[k][i][j], f[k-1][i-set[0]][j-set[1]] + 1);
}
}
}
return f[len][m][n];
}
int[] getSet(String s){int[] set = new int[2];
for(int i = 0; i< s.length(); i++){if(s.charAt(i)-'0' == 0) set[0]++;
else set[1]++;
}
return set;
}
}
先循环 i , j i,j i,j的代码如下:
class Solution {public int findMaxForm(String[] strs, int m, int n) {int len = strs.length;
int[][][] f = new int[len+1][m+1][n+1];
for(int i = 0; i<= m; i++){//先循环i,j
for(int j = 0; j<= n; j++){for(int k = 1; k<= len; k++){String s = strs[k-1];
int[] set = getSet(s);
f[k][i][j] = f[k-1][i][j];
if(i-set[0] >= 0 && j-set[1] >= 0)
f[k][i][j] = Math.max(f[k][i][j], f[k-1][i-set[0]][j-set[1]] + 1);
}
}
}
return f[len][m][n];
}
int[] getSet(String s){int[] set = new int[2];
for(int i = 0; i< s.length(); i++){if(s.charAt(i)-'0' == 0) set[0]++;
else set[1]++;
}
return set;
}
}
既然是01背包,那么肯定可以通过滚动数组的方式将三维优化至二维,减少空间开销(方法核心与01背包空间优化一致),Java代码如下:
class Solution {public int findMaxForm(String[] strs, int m, int n) {int len = strs.length;
int[][] f = new int[m+1][n+1];
for(int k = 1; k<= len; k++){//先循环k
String s = strs[k-1];
int[] set = getSet(s);
for(int i = m; i >= set[0]; i--){//核心点在于i,j的遍历上下界及顺序
for(int j = n; j >= set[1]; j--){f[i][j] = f[i][j];
if(i-set[0] >= 0 && j-set[1] >= 0)
f[i][j] = Math.max(f[i][j], f[i-set[0]][j-set[1]] + 1);
}
}
}
return f[m][n];
}
int[] getSet(String s){int[] set = new int[2];
for(int i = 0; i< s.length(); i++){if(s.charAt(i)-'0' == 0) set[0]++;
else set[1]++;
}
return set;
}
}
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧