????1.一和零

题目：

样例输出和输入：

算法原理：
这道题就是让我们找子集的长度，这个子集满足：当中的0不大于m个，当中的1不大于n个，最后返回最大的子集的长度，所以我们首先想到的是二维费用背包问题，因为有两个限制，这里的背包的限制就是0和1的个数的限制，这里的物品其实就是每个字符串。
状态表示：$dp[i][j][k]$表示从前$i$个物品中选择的所有组合中，满足0的个数不大于m，1的个数不大于n个的所有组合中子集长度最大的那个的长度。
状态转移方程：

这里的a和b代表的是当前i位置字符串中0和1分别的个数，所以我们在进行填表的时候应该遍历一下字符串，将当中的0和1分别记录一下，状态转移方程：

$dp[i][j][k]=max(dp[i-1][j][k],dp[i-1][j-a][k-b])$

初始化：

代码：
未优化的代码：

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n)
    {
        int sz = strs.size();
        vector<vector<vector<int>>> dp(sz + 1, vector<vector<int>>(m + 1, vector<int>(n + 1)));
        for (int i = 1;i <= sz;i++)
        {
            //统计一下字符串中0和1的个数
            int a = 0, b = 0;
            for (auto e : strs[i - 1])
            {
                if (e == '1')b++;
                else a++;
            }
            for (int j = 0;j <= m;j++)
            {
                for (int k = 0;k <= n;k++)
                {
                    dp[i][j][k] = dp[i - 1][j][k];
                    if (j >= a && k >= b)dp[i][j][k] = max(dp[i - 1][j][k], dp[i - 1][j - a][k - b] + 1);
                }
            }
        }
        return dp[sz][m][n];
    }
};

滚动数组优化的代码：

class Solution {
public:
	int findMaxForm(vector<string>& strs, int m, int n)
	{
		int sz = strs.size();
		vector<vector<int>> dp(m + 1, vector<int>(n + 1));
		for (int i = 1;i <= sz;i++)
		{
			//统计一下字符串中0和1的个数
			int a = 0, b = 0;
			for (auto e : strs[i - 1])
			{
				if (e == '1')b++;
				else a++;
			}
			for (int j = m;j >=a;j--)
				for (int k = n;k >=b;k--)
				dp[j][k] = max(dp[j][k], dp[j - a][k - b] + 1);
		}
		return dp[m][n];
	}
};

运行结果：

????2.盈利计划

题目：

样例输出和输入：

算法原理：
这道题每个group对应一个profit，下标是对应的。

根据上面的图片加上题目要求，我们可以得知，我们每次选择的利润必须大于给定的$minProfit$然后每次需要的人口不能超过$n$，最后求出满足这个条件的所有组合有多少种。
状态表示：$dp[i][j][k]$表示从前i个工作计划中选择，人数不超过i的，但是盈利大于k的所有组合数的总和。
状态转移方程：
第一种状态：不选择i位置，$dp[i-1][j][k]$

第二种状态：选择i位置，首先考虑二维$dp[i-1][j-group[i]]$这里我们考虑一下$j-group[i]\le 0$是否成立将group[i]移到右边去可以得到：$j\le group[i]$这个是什么意思呢？表示i工作需要的人口是大于总人口j的，所以这肯定是不可能的，所以这里中只能是$j-group[i]\ge 0$，我们再来考虑三维的：$dp[i-1][j-group[i]][k-profit[i]]$我们来考虑$k-profit[i]\le 0$是否成立，首先我们还是继续移一下项：$k\le profit[i]$这里k表示总的利润，profit表示当前工作产出的利润，所以这里的意思就表示无论前面总利润是多少，这里都都能满足当前的利润，所以我们只需要选择0即可，所以第二种状态：

$dp[i-1][j-group[i]][max(0,k-profit[i])]$

最后这两种状态的总和就是当前状态的所有组合的总和：

$dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j-group[i]][max(0,k-profit[i])]$

代码：
未优化的代码：

class Solution {
public:
    int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) 
    {
        int len = group.size();
        int MOD = 1e9 + 7;
        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(0, k - profit[i - 1])];
                    dp[i][j][k] %= MOD;
                }
            }
        }
        return dp[len][n][minProfit];
    }
};

优化过后的代码：

int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) 
{
	int len = group.size();
	int MOD = 1e9 + 7;
	vector<vector<int>> dp(n + 1, vector<int>(minProfit + 1));
	for (int j = 0;j <= n;j++)dp[j][0] = 1;
	for (int i = 1;i <= len;i++)
		for (int j = n;j >= group[i - 1];j--)
			for (int k = 0;k <= minProfit;k++)
			{
				dp[j][k] += dp[j - group[i - 1]][max(0, k - profit[i - 1])];
				dp[j][k] %= MOD;
			}
	return dp[n][minProfit];
}

运行结果：