[Algo] 三维动态规划

fx1 - 暴力递归, fx2 - 记忆化搜索, fx3 - 严格位置依赖, fx4 - 状态压缩

1. 零和一

// 1. 零和一
// https://leetcode.cn/problems/ones-and-zeroes/
pair<int, int> zerosAndOnes(string &str)
{
    int zeros = 0, ones = 0;
    for (char ch : str)
    {
        if (ch == '0') zeros++;
        else if (ch == '1') ones++;
    }
    return make_pair(zeros, ones);
}
int f11(vector<string>& strs, int i, int z, int o)
{
    if (i == strs.size()) return 0;
    int p1 = f11(strs, i + 1, z, o);
    pair<int, int> zao = zerosAndOnes(strs[i]);
    if (zao.first <= z && zao.second <= o)
    {
        int p2 = f11(strs, i + 1, z - zao.first, o - zao.second);
        return max(p1, 1 + p2);
    }
    else return p1;
}
int f12(vector<string>& strs, int i, int z, int o, vector<vector<vector<int>>> &mem)
{
    if (i == strs.size()) return 0;
    if (mem[i][z][o] != -1) return mem[i][z][o];
    int p1 = f12(strs, i + 1, z, o, mem), ans = p1;
    pair<int, int> zao = zerosAndOnes(strs[i]);
    if (zao.first <= z && zao.second <= o)
    {
        int p2 = f12(strs, i + 1, z - zao.first, o - zao.second, mem);
        ans = max(p1, 1 + p2);
    }
    mem[i][z][o] = ans;
    return ans;
}
int f13(vector<string>& strs, int m, int n, vector<vector<vector<int>>> &dp)
{
    for (int i = strs.size() - 1; i >= 0; i--)
    for (int z = 0; z <= m; z++) for (int o = 0; o <= n; o++)
    {
        dp[i][z][o] = dp[i + 1][z][o];
        pair<int, int> zao = zerosAndOnes(strs[i]);
        if (zao.first <= z && zao.second <= o)
        dp[i][z][o] = max(dp[i + 1][z][o], 1 + dp[i + 1][z - zao.first][o - zao.second]);
    }
    return dp[0][m][n];
}
int f14(vector<string>& strs, int m, int n, vector<vector<int>> &dp)
{
    for (int i = strs.size() - 1; i >= 0; i--)
    {
        pair<int, int> zao = zerosAndOnes(strs[i]);
        for (int z = m; z >= zao.first; z--)
        for (int o = n; o >= zao.second; o--)
        dp[z][o] = max(dp[z][o], 1 + dp[z - zao.first][o - zao.second]);
    }
    return dp[m][n];
}
int findMaxForm(vector<string>& strs, int m, int n) {
    vector<vector<int>> dp(m + 1, vector<int>(n + 1));
    return f14(strs, m, n, dp);
}

2. 盈利计划

// 2. 盈利计划
// https://leetcode.cn/problems/profitable-schemes/description/
long f22(int i, int rest_people, int rest_profit, vector<int>& group, vector<int>& profit, vector<vector<vector<long>>>& mem)
{
    int task = group.size();
    if (mem[i][rest_people][rest_profit] != -1) return mem[i][rest_people][rest_profit];
    long ans;
    if (i == task || rest_people == 0) ans = rest_profit <= 0 ? 1 : 0; // 员工或任务已经耗尽
    else 
    {
        long p1 = f22(i + 1, rest_people, rest_profit, group, profit, mem);
        long p2 = 0;
        if (group[i] <= rest_people) p2 = f22(i + 1, rest_people - group[i], max(0, rest_profit - profit[i]), group, profit, mem);
        ans = (p1 + p2) % 1000000007;
    }
    mem[i][rest_people][rest_profit] = ans;
    return ans;
}
long f23(int n, int minProfit, vector<int>& group, vector<int>& profit, vector<vector<vector<long>>>& dp)
{
    int task = group.size();
    for (int rest_people = 0; rest_people <= n; rest_people++) dp[task][rest_people][0] = 1;
    for (int i = task - 1; i >= 0; i--)
    for (int rest_people = 0; rest_people <= n; rest_people++)
    for (int rest_profit = 0; rest_profit <= minProfit; rest_profit++)
    {
        dp[i][rest_people][rest_profit] = dp[i + 1][rest_people][rest_profit];
        if (group[i] <= rest_people) 
        dp[i][rest_people][rest_profit] = (dp[i][rest_people][rest_profit] + dp[i + 1][rest_people - group[i]][max(0, rest_profit - profit[i])]) % MOD;
    }
    return dp[0][n][minProfit];
}
long f24(int n, int minProfit, vector<int>& group, vector<int>& profit, vector<vector<long>>& dp)
{
    int task = group.size();
    for (int rest_people = 0; rest_people <= n; rest_people++) dp[rest_people][0] = 1;
    for (int i = task - 1; i >= 0; i--)
    for (int rest_people = n; rest_people >= 0; rest_people--)
    for (int rest_profit = minProfit; rest_profit >= 0; rest_profit--)
    {
        if (group[i] <= rest_people) 
        dp[rest_people][rest_profit] = (dp[rest_people][rest_profit] + dp[rest_people - group[i]][max(0, rest_profit - profit[i])]) % MOD;
    }
    return dp[n][minProfit];
}
int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {
    vector<vector<long>> dp(n + 1, vector<long>(minProfit + 1));
    return f24(n, minProfit, group, profit, dp);
}

3. 矩阵中和能被 K 整除的路径

// 3. 矩阵中和能被 K 整除的路径
// https://leetcode.cn/problems/paths-in-matrix-whose-sum-is-divisible-by-k/description/
long f32(int i, int j, long mod, vector<vector<int>>& grid, int k, vector<vector<vector<long>>> &mem)
{
    int n = grid.size(), m = grid[0].size();
    if (i == n || j == m) return 0;
    if (mem[i][j][mod] != -1) return mem[i][j][mod];
    long ans;
    if (i == n - 1 && j == m - 1) ans = (mod + grid[i][j]) % k == 0 ? 1 : 0;
    else ans = (f32(i + 1, j, (mod + grid[i][j]) % k, grid, k, mem) + f32(i, j + 1, (mod + grid[i][j]) % k, grid, k, mem)) % MOD;
    mem[i][j][mod] = ans;
    return ans;
}
int numberOfPaths(vector<vector<int>>& grid, int k) {
    int n = grid.size(), m = grid[0].size(); long sum = 0;
    vector<vector<vector<long>>> mem(n, vector<vector<long>>(m, vector<long>(k, -1)));
    return f32(0, 0, 0, grid, k, mem);
}