2024/08/06 每日一题

XuGui / 2024-08-07 / 原文

LeetCode 3129 找出所有稳定的二进制数组I

方法1：动态规划

第一步：定义 DP 数组

$dp_0[i][j]$：填入 $i$ 个 $0$ 和 $j$ 个 $1$，并且最后填 $0$ 的方案数
$dp_1[i][j]$：填入 $i$ 个 $0$ 和 $j$ 个 $1$，并且最后填 $1$ 的方案数

第二步：状态转移方程

（1）$dp_0[i][j]$ 表示第 $i+j$ 位置将填入 $0$，故 $i+j-1$ 位可能填了 $0$ 或 $1$

$i+j-1$ 位填了 $1$，从 $dp_1[i-1][j]$ 转移，由于其尾部填 $1$，故可以直接转移
$i+j-1$ 位填了 $0$，从$dp_0[i-1][j]$ 转移，但需要判别 $i+j$ 填 $0$ 是否合法
- 如果 $i \leqslant limit$，则 $i+j$ 填入 $0$ 对所有方案 $dp_0[i-1][j]$ 均是合法的
- 如果 $i>limit$，则 $i+j$ 填入 $0$ 对所有方案 $dp_0[i-1][j]$ 中的部分方案是不合法的
  - $i+j$ 填入 $0$ 不合法，即从此方案 $dp_1[i-limit-1][j]$ 开始已经填入了 $limit$ 个 $0$

（2）$dp_1[i][j]$ 表示第 $i+j$ 位置将填入 $1$，故 $i+j-1$ 位可能填了 $0$ 或 $1$

$i+j-1$ 位填了 $0$，从 $dp_0[i][j-1]$ 转移，由于其尾部填 $0$，故可以直接转移
$i+j-1$ 位填了 $1$，从$dp_1[i][j-1]$ 转移，但需要判别 $i+j$ 填 $1$ 是否合法
- 如果 $i \leqslant limit$，则 $i+j$ 填入 $1$ 对所有方案 $dp_1[i][j-1]$ 均是合法的
- 如果 $i>limit$，则 $i+j$ 填入 $1$ 对所有方案 $dp_1[i][j-1]$ 中的部分方案是不合法的
  - $i+j$ 填入 $1$ 不合法，即从此方案 $dp_0[i][j-limit-1]$ 开始已经填入了 $limit$ 个 $1$

第三步：初始化 DP 数组

（1）从第二步可知，$dp_0[i][j]$ 需要知道 $dp_0[i-1][j]$ 和 $dp_1[i-1][j]$，故需要初始化第一行和第一列

如果 $i=0;j=0$，则 $dp_0[0][0]=1$
如果 $i=0;j=1 \cdots one$，$0$ 的个数是 $0$，故 $dp_0[0][j]=0$
如果 $i=1 \cdots zero;j=0$；$1$ 的个数是 $0$，但只能连续填 $limit$ 个 $0$，故 $dp_0[0 \cdots min(zero,limit)][0]=1$，其余为 $0$

（2）从第二步可知，$dp_1[i][j]$ 需要知道 $dp_0[i][j-1]$ 和 $dp_1[i][j-1]$，故需要初始化第一行和第一列

如果 $i=0;j=0$，则 $dp_1[0][0]=1$
如果 $i=1 \cdots zero;j=0$，$1$ 的个数是 $0$，故 $dp_1[i][0]=0$
如果 $i=0;j=1 \cdots one$；$0$ 的个数是 $0$，但只能连续填 $limit$ 个 $1$，故 $dp_1[0][0 \cdots min(one,limit)]=1$，其余为 $0$

class Solution {
    public int numberOfStableArrays(int zero, int one, int limit) {
        int MOD = 1000000007;
        int[][] dp0 = new int[zero + 1][one + 1];
        int[][] dp1 = new int[zero + 1][one + 1];
        for(int i = 0; i <= Math.min(zero, limit); i++)
            dp0[i][0] = 1;
        for(int j = 0; j <= Math.min(one, limit); j++) 
            dp1[0][j] = 1;
        for(int i = 1; i <= zero; i++) {
            for(int j = 1; j <= one; j++) {
                dp0[i][j] = dp1[i - 1][j] + dp0[i - 1][j];
                dp0[i][j] -= i > limit ? dp1[i - 1 - limit][j] : 0;
                // 因为取余后 后面的数可能比前面的数小 故此处不加上 MOD 会导致 dp0[i][j] 变为负数
                dp0[i][j] = (dp0[i][j] % MOD + MOD) % MOD;
                dp1[i][j] = dp0[i][j - 1] + dp1[i][j - 1];
                dp1[i][j] -= j > limit ? dp0[i][j - 1- limit] : 0;
                // 因为取余后 后面的数可能比前面的数小 此处不加上 MOD 会导致 dp1[i][j] 变为负数
                dp1[i][j] = (dp1[i][j] % MOD + MOD) % MOD;
            }
        }
        return (dp0[zero][one] + dp1[zero][one]) % MOD;
    }
}