474. 一和零
474. 一和零
题目描述：
给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。
如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。
解题思路：
算法思路：
先将问题转化成我们熟悉的题型。
i.
在⼀些物品中「挑选」⼀些出来，然后在满⾜某个「限定条件」下，解决⼀些问题，⼤概率
是背包模型；
ii.
由于每⼀个物品都只有
1
个，因此是⼀个「01 背包问题」。
但是，我们发现这⼀道题⾥⾯有「两个限制条件」。因此是⼀个「⼆维费⽤的 01 背包问题」。那
么我们定义状态表⽰的时候，来⼀个三维
dp
表，把第⼆个限制条件加上即可。
1.
状态表⽰：
dp[i][j][k]
表⽰：从前
i
个字符串中挑选，字符
0
的个数不超过
j
，字符
1
的个数不
超过
k
，所有的选法中，最⼤的⻓度。
2.
状态转移⽅程：
线性
dp
状态转移⽅程分析⽅式，⼀般都是「根据最后⼀步」的状况，来分情况讨论。为了⽅便
叙述，我们记第
i
个字符中，字符
0
的个数为
a
，字符
1
的个数为
b
：
i.
不选第
i
个字符串：相当于就是去前
i - 1
个字符串中挑选，并且字符
0
的个数不超
过
j
，字符
1
的个数不超过
k
。此时的最⼤⻓度为
dp[i][j][k] = dp[i - 1]
[j][k]
；
ii.
选择第
i
个字符串：那么接下来我仅需在前
i - 1
个字符串⾥⾯，挑选出来字符
0
的
个数不超过
j - a
，字符
1
的个数不超过
k - b
的最⻓⻓度，然后在这个⻓度后⾯加
上字符串
i
即可。。此时
dp[i][j][k] = dp[i - 1][j - a][k - b] + 1
。
但是这种状态不⼀定存在，因此需要特判⼀下。
综上，状态转移⽅程为：
dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j - a]
[k - b] + 1)
。
3.
初始化：
当没有字符串的时候，没有⻓度，因此初始化为
0
即可。
4.
填表顺序：
保证第⼀维的循环「从⼩到⼤」即可。
5.
返回值：
根据「状态表⽰」，我们返回
dp[len][m][n]
。
其中
len
表⽰字符串数组的⻓度。
6.
空间优化：
所有的「背包问题」，都可以进⾏空间上的优化。
对于「⼆维费⽤的 01 背包」类型的，我们的优化策略是：
i.
删掉第⼀维；
ii.
修改第⼆层以及第三层循环的遍历顺序即可
解题代码：
class Solution {
public:
int f(string s,char ch)
{
int ret=0;
for(int i=0;i<=s.size();i++)
if(s[i]==ch) ret++;
return ret;
}
int findMaxForm(vector<string>& strs, int m, int n) {
int len=strs.size();
vector<vector<vector<int>>>dp(len+1,vector<vector<int>>(m+1,vector<int>(n+1)));
for(int i=1;i<=len;i++)
{
for(int j=0;j<=m;j++)
{
for(int k=0;k<=n;k++)
{
dp[i][j][k]=dp[i-1][j][k];
int a=f(strs[i-1],'0');//0的个数
int b=f(strs[i-1],'1');//1的个数
if(j>=a&&k>=b)
dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-a][k-b]+1);
}
}
}
return dp[len][m][n];
}
};879. 盈利计划
879. 盈利计划
题目描述：
集团里有 n 名员工，他们可以完成各种各样的工作创造利润。
第 i 种工作会产生 profit[i] 的利润，它要求 group[i] 名成员共同参与。如果成员参与了其中一项工作，就不能参与另一项工作。
工作的任何至少产生 minProfit 利润的子集称为 盈利计划 。并且工作的成员总数最多为 n 。
有多少种计划可以选择？因为答案很大，所以 返回结果模 10^9 + 7 的值。
解题思路：
算法思路：
这道题⽬⾮常难读懂，但是如果结合例⼦多读⼏遍，你就会发现是⼀个经典的「⼆维费⽤的背包问
题」。因此我们可以仿照「⼆维费⽤的背包」来定义状态表⽰。
1.
状态表⽰：
dp[i][j][k]
表⽰：从前
i
个计划中挑选，总⼈数不超过
j
，总利润⾄少为
k
，⼀共有多
少种选法。
注意注意注意，这道题⾥⾯出现了⼀个「⾄少」，和我们之前做过的背包问题不⼀样。因此，我们
在分析「状态转移⽅程」的时候要结合实际情况考虑⼀下。
2.
状态转移⽅程：
⽼规矩，根据「最后⼀个位置」的元素，结合题⽬的要求，我们有「选择」最后⼀个元素或者「不
选择」最后⼀个元素两种策略：
i.
不选
i
位置的计划：那我们只能去前
i - 1
个计划中挑选，总⼈数不超过
j
，总利润
⾄少为
k
。此时⼀共有
dp[i - 1][j][k]
种选法；
ii.
选择
i
位置的计划：那我们在前
i - 1
个计划中挑选的时候，限制就变成了，总⼈数不
超过
j - g[i]
，总利润⾄少为
k - p[i]
。此时⼀共有
dp[i - 1][j - g[i]]
[k - p[i]]
。
第⼆种情况下有两个细节需要注意：
1.
j - g[i] < 0
：此时说明
g[i]
过⼤，也就是⼈数过多。因为我们的状态表⽰要
求⼈数是不能超过
j
的，因此这个状态是不合法的，需要舍去。
2.
k - p[i] < 0
：此时说明
p[i]
过⼤，也就是利润太⾼。但是利润⾼，不正是我
们想要的嘛？所以这个状态「不能舍去」。但是问题来了，我们的
dp
表是没有负数的
下标的，这就意味着这些状态我们⽆法表⽰。其实，根本不需要负的下标，我们根据实
际情况来看，如果这个任务的利润已经能够达标了，我们仅需在之前的任务中，挑选出
来的利润⾄少为
0
就可以了。因为实际情况不允许我们是负利润，那么负利润就等价
于利润⾄少为
0
的情况。所以说这种情况就等价于
dp[i][j][0]
，我们可以对
k
- p[i]
的结果与
0
取⼀个
max
。
综上，我们的状态转移⽅程为：
dp[i][j][k] = dp[i - 1][j][k] + dp[i - 1][j - g[i - 1]][max(0, k
- p[i - 1])]
。
3.
初始化：
当没有任务的时候，我们的利润为
0
，此时⽆论⼈数限制为多少，我们都能找到⼀个「空集」的
⽅案。
因此初始化
dp[0][j][0]
的位置为
1
，其中
0 <= j <= n
。
4.
填表顺序：
根据「状态转移⽅程」，我们保证
i
从⼩到⼤即可。
5.
返回值：
根据「状态表⽰」，我们返回
dp[len][m][n]
。
其中
len
表⽰字符串数组的⻓度。
6.
空间优化：
所有的「背包问题」，都可以进⾏空间上的优化。
对于「⼆维费⽤的 01 背包」类型的，我们的优化策略是：
i.
删掉第⼀维；
ii.
修改第⼆层以及第三层循环的遍历顺序即可。
解题代码：
class Solution {
public:
int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {
const int MOD=1e9+7;
int len=group.size();
vector<vector<vector<int>>>dp(len+1,vector<vector<int>>(n+1,vector<int>(minProfit+1)));
for(int j=0;j<=n;j++) dp[0][j][0]=1;
for(int i=1;i<=len;i++)
{
for(int j=0;j<=n;j++)
{
for(int k=0;k<=minProfit;k++)
{
dp[i][j][k]+=dp[i-1][j][k];
if(j>=group[i-1])
dp[i][j][k]+=dp[i-1][j-group[i-1]][max(k-profit[i-1],0)];
dp[i][j][k]%=MOD;
}
}
}
return dp[len][n][minProfit];
}
};
