FZU 2030 括號問題：DFS 枚舉 ? 替換判斷合法性

題目描述

字符串含 (、)、?（長度 ≤ 16）。? 可替換為 ( 或 )。求替換方案數使最終字符串括號匹配。

解題思路：DFS + 剪枝

遞歸函數 dfs(pos, balance)：

• pos：當前處理位置。
• balance：當前未匹配的左括號數（左括號 +1，右括號 -1）。
• 剪枝：balance < 0 直接返回（前綴非法）。
• 終止：pos == len 且 balance == 0，方案數 +1。
• 分支：若 s[pos] == '?'，嘗試 ( 和 ) 兩種；否則按固定字符遞歸。

C++ 代碼實現

#include <cstdio>
#include <cstring>
using namespace std;

char s[20];
int len, ans;

void dfs(int pos, int bal) {
    if (bal < 0) return; // 剪枝：右括號多於左
    if (pos == len) {
        if (bal == 0) ++ans;
        return;
    }
    if (s[pos] == '(') dfs(pos + 1, bal + 1);
    else if (s[pos] == ')') dfs(pos + 1, bal - 1);
    else { // '?'
        dfs(pos + 1, bal + 1); // 當 '('
        dfs(pos + 1, bal - 1); // 當 ')'
    }
}

int main() {
    while (scanf("%s", s) == 1) {
        len = strlen(s);
        ans = 0;
        dfs(0, 0);
        printf("%d\n", ans);
    }
    return 0;
}

複雜度

• 最壞 2^16 = 65536 狀態，DFS 瞬間通過。
• 剪枝 bal < 0 大幅減少搜索空間。