CSDN

三维动态规划

2024-02-01 15:52 由 Sprinining 发表于 #其他

三维动态规划

474. 一和零

  • 多维费用背包
int zeros;
int ones;
int len;

void count(char *s) {
    zeros = 0;
    ones = 0;
    int l = strlen(s);
    for (int i = 0; i < l; ++i) {
        if (s[i] == '0') zeros++;
        if (s[i] == '1') ones++;
    }
}

int max(int a, int b) {
    return a > b ? a : b;
}

// 返回0不超过z，1不超过o时，strs从curIndex下标往后选，最大的子集长度
int recursive(char **strs, int curIndex, int z, int o) {
    if (curIndex == len) return 0;
    // 不选中
    int p1 = recursive(strs, curIndex + 1, z, o);
    // 选中strs[curIndex]
    int p2 = 0;
    count(strs[curIndex]);
    if (zeros <= z && ones <= o)
        p2 = 1 + recursive(strs, curIndex + 1, z - zeros, o - ones);
    return max(p1, p2);
}

// 暴力超时
int findMaxForm(char **strs, int strsSize, int m, int n) {
    len = strsSize;
    return recursive(strs, 0, m, n);
}

int zeros;
int ones;
int len;

void count(char *s) {
    zeros = 0;
    ones = 0;
    int l = strlen(s);
    for (int i = 0; i < l; ++i) {
        if (s[i] == '0') zeros++;
        if (s[i] == '1') ones++;
    }
}

int max(int a, int b) {
    return a > b ? a : b;
}

int ***dp;

// 返回0不超过z，1不超过o时，strs从curIndex下标往后选，最大的子集长度
int recursive(char **strs, int curIndex, int z, int o) {
    if (curIndex == len) return 0;
    if (dp[curIndex][z][o] != -1) return dp[curIndex][z][o];
    // 不选中
    int p1 = recursive(strs, curIndex + 1, z, o);
    // 选中strs[curIndex]
    int p2 = 0;
    count(strs[curIndex]);
    if (zeros <= z && ones <= o)
        p2 = 1 + recursive(strs, curIndex + 1, z - zeros, o - ones);
    int res = max(p1, p2);
    dp[curIndex][z][o] = res;
    return res;
}

// 自上而下记忆化搜索
int findMaxForm(char **strs, int strsSize, int m, int n) {
    len = strsSize;
    dp = (int ***) malloc(sizeof(int **) * len);
    for (int i = 0; i < len; ++i)
        dp[i] = (int **) malloc(sizeof(int *) * (m + 1));
    for (int i = 0; i < len; ++i) {
        for (int j = 0; j <= m; ++j) {
            dp[i][j] = (int *) malloc(sizeof(int) * (n + 1));
            memset(dp[i][j], -1, sizeof(int) * (n + 1));
        }
    }
    return recursive(strs, 0, m, n);
}

int zeros;
int ones;

void count(char *s) {
    zeros = 0;
    ones = 0;
    int l = strlen(s);
    for (int i = 0; i < l; ++i) {
        if (s[i] == '0') zeros++;
        if (s[i] == '1') ones++;
    }
}

int max(int a, int b) {
    return a > b ? a : b;
}

// 自底向上
int findMaxForm(char **strs, int strsSize, int m, int n) {
    // 返回0不超过z，1不超过o时，strs从curIndex下标往后选，最大的子集长度
    int dp[strsSize + 1][m + 1][n + 1];
    // 最上层strsSize层全0，即strs从strsSize下标往后选，最大的子集长度是0，因为没有字符串可选
    for (int i = 0; i <= m; ++i)
        for (int j = 0; j <= n; ++j)
            dp[strsSize][i][j] = 0;
    // 从strsSize-1层往下填写每个二维表
    for (int curIndex = strsSize - 1; curIndex >= 0; curIndex--) {
        count(strs[curIndex]);
        // 当前层只依赖与上层的元素
        for (int z = 0, p1, p2; z <= m; ++z) {
            for (int o = 0; o <= n; ++o) {
                p1 = dp[curIndex + 1][z][o];
                p2 = 0;
                if (zeros <= z && ones <= o)
                    p2 = 1 + dp[curIndex + 1][z - zeros][o - ones];
                dp[curIndex][z][o] = max(p1, p2);
            }
        }
    }
    return dp[0][m][n];
}


int zeros;
int ones;

void count(char *s) {
    zeros = 0;
    ones = 0;
    int l = strlen(s);
    for (int i = 0; i < l; ++i) {
        if (s[i] == '0') zeros++;
        if (s[i] == '1') ones++;
    }
}

int max(int a, int b) {
    return a > b ? a : b;
}

// 空间压缩
int findMaxForm(char **strs, int strsSize, int m, int n) {
    // 返回0不超过z，1不超过o时，strs从curIndex下标往后选，最大的子集长度
    int dp[m + 1][n + 1];
    // 最上层strsSize层全0，即strs从strsSize下标往后选，最大的子集长度是0，因为没有字符串可选
    for (int i = 0; i <= m; ++i)
        memset(dp[i], 0, sizeof(int) * (n + 1));
    // 从strsSize-1层往下填写每个二维表（实际上和遍历字符串的顺序无关）
    for (int i = strsSize - 1; i >= 0; i--) {
        count(strs[i]);
        // 当前层只依赖与上层的元素，从上往下，从右往左更新当前层，这样左下角尚未跟新的元素实际就是上一层的元素
        // 依赖于上一层同一位置的元素和上一层同一位置的左下角区域的所有元素
        for (int z = m; z >= zeros; z--)
            for (int o = n; o >= ones; o--)
                dp[z][o] = max(dp[z][o], dp[z - zeros][o - ones] + 1);
    }
    return dp[m][n];
}

879. 盈利计划

  • 多维费用背包
int *g;
int *p;
int gSize;
const int MOD = 1e9 + 7;

// 到i号工作，人数还剩r，利润还有s才达标
int recursive(int r, int s, int i) {
    // 人数用尽，判断利润是否达标
    if (r <= 0) return s <= 0 ? 1 : 0;
    // 工作用尽，判断利润是否达标
    if (i == gSize) return s <= 0 ? 1 : 0;
    // 情况1：要当前工作
    int p1 = recursive(r, s, i + 1);
    // 情况2：不要当前工作
    int p2 = 0;
    if (g[i] <= r)
        p2 = recursive(r - g[i], s - p[i], i + 1);
    return (p1 + p2) % MOD;
}

// 暴力超时
int profitableSchemes(int n, int minProfit, int *group, int groupSize, int *profit, int profitSize) {
    p = profit;
    g = group;
    gSize = groupSize;
    return recursive(n, minProfit, 0);
}

int *g;
int *p;
int gSize;
const int MOD = 1e9 + 7;
int ***dp;

int max(int a, int b) {
    return a > b ? a : b;
}

// 到i号工作，人数还剩r，利润还有s才达标
int recursive(int r, int s, int i) {
    // 人数用尽，判断利润是否达标
    if (r <= 0) return s <= 0 ? 1 : 0;
    // 工作用尽，判断利润是否达标
    if (i == gSize) return s <= 0 ? 1 : 0;
    if (dp[i][r][s] != -1) return dp[i][r][s];
    // 情况1：要当前工作
    int p1 = recursive(r, s, i + 1);
    // 情况2：不要当前工作
    int p2 = 0;
    // 利润达标了，但人数没耗尽，后续的可能也要计算
    // 利润变成负数或0都能表示利润达标，但是负数不在dp表的下标范围内
    if (g[i] <= r)
        p2 = recursive(r - g[i], max(s - p[i], 0), i + 1);
    dp[i][r][s] = (p1 + p2) % MOD;
    return dp[i][r][s];
}

// 自顶向下记忆化搜索
int profitableSchemes(int n, int minProfit, int *group, int groupSize, int *profit, int profitSize) {
    p = profit;
    g = group;
    gSize = groupSize;
    dp = (int ***) malloc(sizeof(int **) * groupSize);
    for (int i = 0; i < groupSize; ++i)
        dp[i] = (int **) malloc(sizeof(int *) * (n + 1));
    for (int i = 0; i < groupSize; ++i) {
        for (int j = 0; j <= n; ++j) {
            dp[i][j] = (int *) malloc(sizeof(int) * (minProfit + 1));
            memset(dp[i][j], -1, sizeof(int) * (minProfit + 1));
        }
    }

    return recursive(n, minProfit, 0);
}

int max(int a, int b) {
    return a > b ? a : b;
}

// 空间压缩
int profitableSchemes(int n, int minProfit, int *group, int groupSize, int *profit, int profitSize) {
    const int MOD = 1e9 + 7;
    int dp[n + 1][minProfit + 1];
    for (int i = 0; i <= n; ++i)
        for (int j = 0; j <= minProfit; ++j)
            dp[i][j] = 0;
    // 从最上一层，i == groupSize越界的时候开始填
    for (int r = 0; r <= n; ++r) dp[r][0] = 1;
    for (int i = groupSize - 1; i >= 0; i--) {
        // dp没更新前代表上一层二维表
        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]][max(s - profit[i], 0)] : 0;
                dp[r][s] = (p1 + p2) % MOD;
            }
        }
    }
    return dp[n][minProfit];
}

688. 骑士在棋盘上的概率

double ***dp;

// 从(i, j)出发，还剩k步要走
double recursive(int n, int i, int j, int k) {
    // 越界
    if (i < 0 || i >= n || j < 0 || j >= n) return 0;
    if (dp[i][j][k] != -1) return dp[i][j][k];
    double res = 0;
    if (k == 0) {
        // 仍在棋盘上
        res = 1;
    } else {
        // 八个位置，每个位置概率八分之一
        res += (recursive(n, i - 2, j + 1, k - 1) / 8);
        res += (recursive(n, i - 1, j + 2, k - 1) / 8);
        res += (recursive(n, i + 1, j + 2, k - 1) / 8);
        res += (recursive(n, i + 2, j + 1, k - 1) / 8);
        res += (recursive(n, i + 2, j - 1, k - 1) / 8);
        res += (recursive(n, i + 1, j - 2, k - 1) / 8);
        res += (recursive(n, i - 1, j - 2, k - 1) / 8);
        res += (recursive(n, i - 2, j - 1, k - 1) / 8);
    }
    dp[i][j][k] = res;
    return res;
}

// 记忆化搜索
double knightProbability(int n, int k, int row, int column) {
    dp = (double ***) malloc(sizeof(double **) * n);
    for (int i = 0; i < n; ++i)
        dp[i] = (double **) malloc(sizeof(double *) * n);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            dp[i][j] = (double *) malloc(sizeof(double) * (k + 1));
            for (int l = 0; l < k + 1; ++l) {
                dp[i][j][l] = -1;
            }
        }
    }
    return recursive(n, row, column, k);
}

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

const int MOD = 1e9 + 7;
int rowSize;
int columnSize;

// 从(i, j)出发，走到右下角，有多少条路径的累加和模k的余数是0
// 如果dp的第三维度是sum，那么数组大小不确定，而且从前面到当前位置的sum可能性很多
long long recursive(int **grid, int i, int j, int k, int sum) {
    // 越界
    if (i >= rowSize || j >= columnSize) return 0;
    // 累加当前格子
    sum += grid[i][j];
    // 到终点，且能被整除
    if (i == rowSize - 1 && j == columnSize - 1 && (sum % k == 0)) {
        return 1;
    }
    // 往下往右
    return (recursive(grid, i + 1, j, k, sum) + recursive(grid, i, j + 1, k, sum)) % MOD;
}

// 暴力超时
int numberOfPaths(int **grid, int gridSize, int *gridColSize, int k) {
    rowSize = gridSize;
    columnSize = *gridColSize;
    return recursive(grid, 0, 0, k, 0);
}

const int MOD = 1e9 + 7;
int rowSize;
int columnSize;
int ***dp;

// 从(i, j)出发，走到右下角，有多少条路径的累加和模k的余数是r
// 如果dp的第三维度是r，那么数组大小确定是k
long long recursive(int **grid, int i, int j, int k, int r) {
    // 越界
    if (i >= rowSize || j >= columnSize) return 0;
    // 到终点，且能被整除
    if (i == rowSize - 1 && j == columnSize - 1 && (grid[i][j] % k == r)) {
        return 1;
    }
    // 后面要凑出来的余数
    int need = (r - (grid[i][j] % k) + k) % k;
    return (recursive(grid, i + 1, j, k, need) + recursive(grid, i, j + 1, k, need)) % MOD;
}

// 暴力超时
int numberOfPaths(int **grid, int gridSize, int *gridColSize, int k) {
    rowSize = gridSize;
    columnSize = *gridColSize;
    return recursive(grid, 0, 0, k, 0);
}

const int MOD = 1e9 + 7;
int rowSize;
int columnSize;
int ***dp;

// 从(i, j)出发，走到右下角，有多少条路径的累加和模k的余数是r
long long recursive(int **grid, int i, int j, int k, int r) {
    // 越界
    if (i >= rowSize || j >= columnSize) return 0;
    // 到终点，且能凑出需要的余数
    if (i == rowSize - 1 && j == columnSize - 1 && (grid[i][j] % k == r)) return 1;
    if (dp[i][j][r] != -1) return dp[i][j][r];
    // 后面要凑出来的余数
    int need = (r - (grid[i][j] % k) + k) % k;
    int res = (recursive(grid, i + 1, j, k, need) + recursive(grid, i, j + 1, k, need)) % MOD;
    dp[i][j][r] = res;
    return res;
}

// 记忆化搜索
int numberOfPaths(int **grid, int gridSize, int *gridColSize, int k) {
    rowSize = gridSize;
    columnSize = *gridColSize;
    // 记录当前坐标，和到到当前位置的r
    dp = (int ***) malloc(sizeof(int **) * rowSize);
    for (int i = 0; i < rowSize; ++i)
        dp[i] = (int **) malloc(sizeof(int *) * columnSize);
    for (int i = 0; i < rowSize; ++i) {
        for (int j = 0; j < columnSize; ++j) {
            dp[i][j] = (int *) malloc(sizeof(int) * k);
            memset(dp[i][j], -1, sizeof(int) * k);
        }
    }
    return recursive(grid, 0, 0, k, 0);
}

const int MOD = 1e9 + 7;
int rowSize;
int columnSize;

int numberOfPaths(int **grid, int gridSize, int *gridColSize, int k) {
    rowSize = gridSize;
    columnSize = *gridColSize;
    // 看成二维表，表中每个元素有k层
    int dp[rowSize][columnSize][k];
    // 静态数组的所有元素都是连续分配
    memset(dp, 0, sizeof(int) * rowSize * columnSize * k);
    // 到终点，且能凑出需要的余数，其他位置都已初始化为0
    dp[rowSize - 1][columnSize - 1][grid[rowSize - 1][columnSize - 1] % k] = 1;

    // 每个格子只依赖于右边和下边的格子
    // 从下往上推最后一列
    for (int i = rowSize - 2; i >= 0; i--)
        for (int r = 0; r < k; ++r)
            dp[i][columnSize - 1][r] = dp[i + 1][columnSize - 1][(k + r - grid[i][columnSize - 1] % k) % k];
    // 从右往左推最后一行
    for (int j = columnSize - 2; j >= 0; j--)
        for (int r = 0; r < k; ++r)
            dp[rowSize - 1][j][r] = dp[rowSize - 1][j + 1][(k + r - grid[rowSize - 1][j] % k) % k];

    for (int i = rowSize - 2; i >= 0; i--) {
        for (int j = columnSize - 2; j >= 0; j--) {
            for (int r = 0; r < k; ++r) {
                int need = (k + r - grid[i][j] % k) % k;
                dp[i][j][r] = (dp[i + 1][j][need] + dp[i][j + 1][need]) % MOD;
            }
        }
    }
    return dp[0][0][0];
}

87. 扰乱字符串

// 返回s1[l1...r1]和s2[l2...r2]是否是扰乱串
bool recursive(char *s1, char *s2, int l1, int r1, int l2, int r2) {
    // 每次比较的都是等长的字符串

    // 都只有一个字符时
    if (l1 == r1) return s1[l1] == s2[l2];

    // 左右两部分等长
    // s1[l1...i][i+1...r1]
    // s2[l2...j][j+2...r2]
    for (int i = l1, j = l2; i < r1; i++, j++)
        if (recursive(s1, s2, l1, i, l2, j) && recursive(s1, s2, i + 1, r1, j + 1, r2))
            return true;

    // s1左等于s2右
    // s1[l1...i][i+1...r1]
    // s2[l2...j-1][j...r2]
    for (int i = l1, j = r2; i < r1; i++, j--)
        if (recursive(s1, s2, l1, i, j, r2) && recursive(s1, s2, i + 1, r1, l2, j - 1))
            return true;
    return false;
}

// 暴力超时
bool isScramble(char *s1, char *s2) {
    return recursive(s1, s2, 0, strlen(s1) - 1, 0, strlen(s2) - 1);
}

// 返回s1从l1开始和s2从l2开始长度为len的字符串是否是扰乱串
bool recursive(char *s1, char *s2, int l1, int l2, int len) {
    // 每次比较的都是等长的字符串

    // 都只有一个字符时
    if (len == 1) return s1[l1] == s2[l2];

    // 左右两部分等长，左k右len-k
    // s1[l1...i][i+1...r1]
    // s2[l2...j][j+2...r2]
    for (int k = 1; k < len; ++k)
        if (recursive(s1, s2, l1, l2, k) && recursive(s1, s2, l1 + k, l2 + k, len - k))
            return true;

    // s1左等于s2右
    // s1[l1...i][i+1...r1]
    // s2[l2...j-1][j...r2]
    for (int i = l1 + 1, j = l2 + len - 1, k = 1; k < len; i++, j--, k++)
        if (recursive(s1, s2, l1, j, k) && recursive(s1, s2, i, l2, len - k))
            return true;
    return false;
}

// 暴力超时，减少了一个参数
bool isScramble(char *s1, char *s2) {
    return recursive(s1, s2, 0, 0, strlen(s1));
}


int ***dp;

// 返回s1从l1开始和s2从l2开始长度为len的字符串是否是扰乱串
bool recursive(char *s1, char *s2, int l1, int l2, int len) {
    // 都只有一个字符时
    if (len == 1) return s1[l1] == s2[l2];

    if (dp[l1][l2][len] != 0) return dp[l1][l2][len] == 1;

    bool res = false;
    // 左右两部分等长，左k右len-k
    // s1[l1...i][i+1...r1]
    // s2[l2...j][j+2...r2]
    for (int k = 1; k < len; ++k)
        if (recursive(s1, s2, l1, l2, k) && recursive(s1, s2, l1 + k, l2 + k, len - k)) {
            res = true;
            break;
        }

    // s1左等于s2右
    // s1[l1...i][i+1...r1]
    // s2[l2...j-1][j...r2]
    if (!res) {
        for (int i = l1 + 1, j = l2 + len - 1, k = 1; k < len; i++, j--, k++)
            if (recursive(s1, s2, l1, j, k) && recursive(s1, s2, i, l2, len - k)) {
                res = true;
                break;
            }
    }
    dp[l1][l2][len] = res ? 1 : -1;
    return res;
}

// 记忆化搜索
bool isScramble(char *s1, char *s2) {
    int length = strlen(s1);
    // 0：未处理；-1：返回false；1：返回true
    dp = (int ***) malloc(sizeof(int **) * length);
    for (int i = 0; i < length; ++i)
        dp[i] = (int **) malloc(sizeof(int *) * length);
    for (int i = 0; i < length; ++i) {
        for (int j = 0; j < length; ++j) {
            dp[i][j] = (int *) malloc(sizeof(int) * (length + 1));
            memset(dp[i][j], 0, sizeof(int) * (length + 1));
        }
    }
    return recursive(s1, s2, 0, 0, length);
}

// 自下而上
bool isScramble(char *s1, char *s2) {
    int length = strlen(s1);
    // 0：未处理；-1：返回false；1：返回true
    bool dp[length][length][length + 1];
    memset(dp, 0, sizeof(bool) * length * length * (length + 1));
    // len=1
    for (int l1 = 0; l1 < length; ++l1)
        for (int l2 = 0; l2 < length; ++l2)
            dp[l1][l2][1] = s1[l1] == s2[l2];
    for (int len = 2; len <= length; ++len) {
        for (int l1 = 0; l1 <= length - len; ++l1) {
            for (int l2 = 0; l2 <= length - len; ++l2) {
                for (int k = 1; k < len; ++k) {
                    if (dp[l1][l2][k] && dp[l1 + k][l2 + k][len - k]) {
                        dp[l1][l2][len] = true;
                        break;
                    }
                }
                if (!dp[l1][l2][len]) {
                    for (int i = l1 + 1, j = l2 + len - 1, k = 1; k < len; i++, j--, k++) {
                        if (dp[l1][j][k] && dp[i][l2][len - k]) {
                            dp[l1][l2][len] = true;
                            break;
                        }
                    }
                }
            }
        }
    }
    return dp[0][0][length];
}

热门相关：12年级的失败   国家性生活管理委员会   哭泣的年轻母亲   b罩杯水多火辣的小姨子   1号婚令：早安，大总裁！