นิพจน์วงเล็บสมดุลที่ตำแหน่งกำหนดต้องเป็นวงเล็บเปิดใน C++

โจทย์ปัญหา

ได้รับจำนวนเต็ม n และอาร์เรย์ position[] ขนาด 2n (1-based indexing) โดย position[i] = 1 หมายถึงตำแหน่ง i ต้องเป็นวงเล็บเปิด '[' หา จำนวนวิธี สร้างนิพจน์วงเล็บสมดุลที่ถูกต้อง

ตัวอย่าง

นำเข้า: n = 2, position = [1, 0, 0, 0] (ตำแหน่ง 1 ต้องเป็น '[')
ผลลัพธ์: 2
วิธีที่เป็นไปได้: [ ] [ ] และ [ [ ] ]

แนวคิดการแก้ปัญหา (Recursion + Memoization)

State: dp[index][open]

• index = ตำแหน่งปัจจุบัน (0 ถึง 2n-1)
• open = จำนวนวงเล็บเปิดที่ยังไม่ปิด (Balance)

Transition:

• ถ้า open < 0 → Invalid (ปิดมากกว่าเปิด) → Return 0
• ถ้า index == 2n:
  • open == 0 → Valid → Return 1
  • Else → Return 0
• ถ้า position[index] == 1 (บังคับเปิด):
  • Return dp(index+1, open+1)
• Else (เลือกได้):
  • Return dp(index+1, open+1) + dp(index+1, open-1)

โค้ดตัวอย่าง (C++) - Recursive + Memoization

#include <bits/stdc++.h>
using namespace std;

#define MAX_N 1000
int dp[MAX_N][MAX_N];

int countWays(int index, int open, int n, const vector<int>& pos) {
    if (open < 0) return 0;
    if (index == 2 * n) {
        return (open == 0) ? 1 : 0;
    }
    if (dp[index][open] != -1) return dp[index][open];

    int ans = 0;
    if (pos[index] == 1) {
        ans = countWays(index + 1, open + 1, n, pos);
    } else {
        ans = countWays(index + 1, open + 1, n, pos)  // วาง '['
            + countWays(index + 1, open - 1, n, pos); // วาง ']'
    }
    return dp[index][open] = ans;
}

int main() {
    int n = 2;
    vector<int> pos = {1, 0, 0, 0};  // ตำแหน่ง 1 ต้องเป็น '['
    memset(dp, -1, sizeof(dp));
    cout << countWays(0, 0, n, pos) << endl;  // Output: 2
    return 0;
}

ผลลัพธ์

2

Complexity Analysis

• States: index (0..2n) × open (0..n) = O(n²)
• Time: O(n²)
• Space: O(n²)

คำอธิบายเพิ่มเติม

• โจทย์นี้เกี่ยวข้องกับ Catalan Numbers (จำนวนนิพจน์วงเล็บสมดุลทั้งหมด = C_n = (2n)!/(n!(n+1)!))
• Constraint position[] ทำให้เป็น Constrained Catalan Problem
• สามารถทำ Bottom-up DP ได้เช่นกัน
• ใช้ long long หรือ BigInteger สำหรับ n ใหญ่เพราะคำตอบโตเร็วมาก

ตัวอย่างเพิ่มเติม