069从递归入手三维动态规划

尝试函数有3个可变参数可以完全决定返回值
题目一

package class069;

// 一和零(多维费用背包)
// 给你一个二进制字符串数组 strs 和两个整数 m 和 n
// 请你找出并返回 strs 的最大子集的长度
// 该子集中 最多 有 m 个 0 和 n 个 1
// 如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集
// 测试链接 : https://leetcode.cn/problems/ones-and-zeroes/
class Solution {
    public static int zeros, ones;

	// 统计一个字符串中0的1的数量
	// 0的数量赋值给全局变量zeros
	// 1的数量赋值给全局变量ones
	public static void zerosAndOnes(String str) {
		zeros = 0;
		ones = 0;
		for (int i = 0; i < str.length(); i++) {
			if (str.charAt(i) == '0') {
				zeros++;
			} else {
				ones++;
			}
		}
	}
	public static int findMaxForm(String[] strs, int m, int n) {
		int len = strs.length;
		int[][][] dp = new int[len + 1][m + 1][n + 1];
		for (int i = len - 1; i >= 0; i--) {
			zerosAndOnes(strs[i]);
			for (int z = 0, p1, p2; z <= m; z++) {
				for (int o = 0; o <= n; o++) {
					p1 = dp[i + 1][z][o];
					p2 = 0;
					if (zeros <= z && ones <= o) {
						p2 = 1 + dp[i + 1][z - zeros][o - ones];
					}
					dp[i][z][o] = Math.max(p1, p2);
				}
			}
		}
		return dp[0][m][n];
	}
}

题目二

package class069;

// 盈利计划(多维费用背包)
// 集团里有 n 名员工，他们可以完成各种各样的工作创造利润
// 第 i 种工作会产生 profit[i] 的利润，它要求 group[i] 名成员共同参与
// 如果成员参与了其中一项工作，就不能参与另一项工作
// 工作的任何至少产生 minProfit 利润的子集称为 盈利计划
// 并且工作的成员总数最多为 n
// 有多少种计划可以选择？因为答案很大，答案对 1000000007 取模
// 测试链接 : https://leetcode.cn/problems/profitable-schemes/

	public static int profitableSchemes3(int n, int minProfit, int[] group, int[] profit) {
		// i = 没有工作的时候，i == g.length
		int[][] dp = new int[n + 1][minProfit + 1];
		for (int r = 0; r <= n; r++) {
			dp[r][0] = 1;
		}
		int m = group.length;
		for (int i = m - 1; i >= 0; i--) {
			for (int r = n; r >= 0; r--) {
				for (int s = minProfit; s >= 0; s--) {
					int p1 = dp[r][s];
					int p2 = group[i] <= r ? dp[r - group[i]][Math.max(0, s - profit[i])] : 0;
					dp[r][s] = (p1 + p2) % mod;
				}
			}
		}
		return dp[n][minProfit];
	}