📘 題目敘述
給你三個正整數 zero、one 和 limit。
如果一個二元陣列 arr 滿足以下條件，就稱它是 stable：
arr中0出現的次數恰好是zeroarr中1出現的次數恰好是onearr中每一個長度大於limit的子陣列，都必須同時包含0和1
請回傳 stable binary arrays 的總數。
由於答案可能非常大，請將結果對 10^9 + 7 取模後回傳。
條件限制
1 <= zero, one, limit <= 200
🧠 解題思路
這題的重點不是只看目前放了幾個 0 跟幾個 1，還要知道：
- 最後一個數字是什麼
- 最後連續出現了幾個一樣的數字
因為題目限制的是：不能出現長度超過 limit 的全 0 或全 1 子陣列。換句話說，就是 同一個數字最多只能連續出現 limit 次。
所以這題很適合用 DP 紀錄狀態。
我這份程式的做法是：
z表示目前已經用了幾個0o表示目前已經用了幾個1b表示目前最後一個數字是0還是1l表示目前尾端連續幾個b
只要知道這四個資訊，就能決定下一步可不可以再放同樣的數字，或是改放另一種數字。
也就是說，這題的核心就是：
用
dp[z][o][b][l]表示：目前已經用了z個0、o個1，最後一個數字是b，而且尾端連續有l個b的 stable array 數量。
接下來就從這個狀態去轉移：
- 如果最後是
0- 還可以再放
0，前提是z < zero且l < limit - 也可以改放
1，前提是o < one
- 還可以再放
- 如果最後是
1- 還可以再放
1，前提是o < one且l < limit - 也可以改放
0，前提是z < zero
- 還可以再放
最後把所有剛好用完 zero 個 0、one 個 1 的合法狀態加總起來，就是答案。
所有變數
dp[201][201][2][201]：DP 陣列，dp[z][o][b][l]表示目前已用z個0、o個1，最後數字是b，尾端連續長度是l的合法陣列數量MOD：模數1000000007z：目前 DP 狀態中已經使用的0的數量o：目前 DP 狀態中已經使用的1的數量b：目前最後一個數字，0代表最後是0，1代表最後是1l：目前尾端連續相同數字的長度now：目前這個 DP 狀態的方案數ans：最後答案k：最後加總答案時，枚舉尾端連續長度用的變數
🪜 主要流程步驟
1. 定義 DP 狀態
先開一個四維 DP：
dp[z][o][b][l]它代表：
- 已經用了
z個0 - 已經用了
o個1 - 最後一個數字是
b - 最後連續有
l個b
這樣的設計很重要，因為題目限制跟「尾端連續長度」直接有關，所以不能只記錄用了幾個 0 和 1。
2. 初始化長度為 1 的情況
一開始可以先放一個 0，或者先放一個 1：
dp[1][0][0][1] = 1;
dp[0][1][1][1] = 1;意思是：
- 用 1 個
0、0 個1，最後是0，而且尾端連續 1 個0，有 1 種 - 用 0 個
0、1 個1，最後是1，而且尾端連續 1 個1，有 1 種
這就是整個 DP 的起點。
3. 枚舉所有可能的狀態
接著用四層迴圈枚舉所有可能的 DP 狀態：
z：從0到zeroo：從0到oneb：0或1l：從1到limit
每次先取出目前這格的方案數：
int now = dp[z][o][b][l];如果這格是 0，代表目前沒有任何合法方法走到這個狀態，就直接跳過：
if (now == 0) {
continue;
}4. 如果最後一個數字是 0，就考慮接下來放什麼
當 b == 0 時，代表目前陣列最後是 0。
這時有兩種選擇。
第一種是再放一個 0：
if (z < zero && l < limit) {
dp[z + 1][o][0][l + 1] += now;
dp[z + 1][o][0][l + 1] %= MOD;
}這段表示：
- 還有
0可以用，也就是z < zero - 而且目前尾端連續
0的長度還沒到上限，也就是l < limit
那就可以再接一個 0，所以：
z + 1o不變- 最後仍然是
0 - 尾端連續長度從
l變成l + 1
第二種是改放一個 1：
if (o < one) {
dp[z][o + 1][1][1] += now;
dp[z][o + 1][1][1] %= MOD;
}這時因為尾端數字從 0 換成 1，所以新的連續長度要重設成 1。
5. 如果最後一個數字是 1，就考慮接下來放什麼
當 b == 1 時，邏輯完全對稱。
如果還能再放 1，而且連續長度還沒超過 limit：
if (o < one && l < limit) {
dp[z][o + 1][1][l + 1] += now;
dp[z][o + 1][1][l + 1] %= MOD;
}這表示：
- 再補一個
1 o增加- 最後仍然是
1 - 尾端連續長度變成
l + 1
如果要改放 0：
if (z < zero) {
dp[z + 1][o][0][1] += now;
dp[z + 1][o][0][1] %= MOD;
}這時最後數字變成 0，所以尾端連續長度重新變成 1。
6. 為什麼這樣就能保證 stable
題目說，任何長度大於 limit 的子陣列都必須同時包含 0 和 1。
這句其實等價於：
- 不能有連續超過
limit個0 - 不能有連續超過
limit個1
而這份程式正是靠 l < limit 這個條件，保證不會把同樣的數字接到超過上限。
所以只要這個 DP 狀態合法，往後的轉移也都合法。
7. 最後把所有剛好用完 zero 和 one 的狀態加總
最後答案不是只看某一個固定 l，因為尾端連續長度可能是 1、2、...、limit。
所以要把：
dp[zero][one][0][k]dp[zero][one][1][k]
全部加起來：
for (int k = 1; k <= limit; k++) {
ans = (ans + dp[zero][one][0][k]) % MOD;
ans = (ans + dp[zero][one][1][k]) % MOD;
}這樣就把所有：
- 用完
zero個0 - 用完
one個1 - 最後可能是
0或1 - 尾端連續長度任意合法值
的 stable arrays 全部統計進去了。
⏱️ 複雜度
- 時間複雜度：
O(zero * one * limit)
四維狀態中，b只有 2 種，所以可視為常數。 - 空間複雜度：
O(zero * one * limit)
需要一個四維 DP 陣列來記錄狀態。
💻 程式碼實作
class Solution {
public:
int numberOfStableArrays(int zero, int one, int limit) {
static int dp[201][201][2][201]; // 已用0、已用1、最後數字、最後長度
memset(dp, 0, sizeof(dp));
dp[1][0][0][1] = 1;
dp[0][1][1][1] = 1;
const int MOD = 1000000007;
for (int z = 0; z <= zero; z++) {
for (int o = 0; o <= one; o++) {
for (int b = 0; b < 2; b++) {
for (int l = 1; l <= limit; l++) {
int now = dp[z][o][b][l];
if (now == 0) {
continue;
}
if (b == 0) {
if (z < zero && l < limit) { // 再放0
dp[z + 1][o][0][l + 1] += now;
dp[z + 1][o][0][l + 1] %= MOD;
}
if (o < one) { // 再放1
dp[z][o + 1][1][1] += now;
dp[z][o + 1][1][1] %= MOD;
}
} else {
if (o < one && l < limit) { // 再放0
dp[z][o + 1][1][l + 1] += now;
dp[z][o + 1][1][l + 1] %= MOD;
}
if (z < zero) { // 再放1
dp[z + 1][o][0][1] += now;
dp[z + 1][o][0][1] %= MOD;
}
}
}
}
}
}
int ans = 0;
for (int k = 1; k <= limit; k++) {
ans = (ans + dp[zero][one][0][k]) % MOD;
ans = (ans + dp[zero][one][1][k]) % MOD;
}
return ans;
}
};🔗 題目連結
https://leetcode.com/problems/find-all-possible-stable-binary-arrays-i/