動態規劃進階 — Bitmask DP、Digit DP 與空間優化技巧 | 資料結構與演算法

function maxCoins(nums: number[]): number {
  // 在兩端加入虛擬氣球 1，避免邊界特殊處理
  const arr = [1, ...nums, 1];
  const n = arr.length;

  // dp[l][r] = 戳破開區間 (l, r) 內所有氣球的最大硬幣數
  // 注意是開區間：l 和 r 本身不被戳，作為邊界存在
  const dp: number[][] = Array.from({ length: n }, () => new Array(n).fill(0));

  // 外層枚舉區間長度（最小為 2，因為是開區間，至少包含一個元素）
  for (let len = 2; len < n; len++) {
    for (let l = 0; l + len < n; l++) {
      const r = l + len;
      // 枚舉最後一個被戳破的氣球 k（在開區間 (l, r) 內）
      for (let k = l + 1; k < r; k++) {
        // k 被戳破時，左側 (l, k) 和右側 (k, r) 已清空，鄰居是 arr[l] 和 arr[r]
        const coins = arr[l] * arr[k] * arr[r];
        dp[l][r] = Math.max(dp[l][r], dp[l][k] + coins + dp[k][r]);
      }
    }
  }

  return dp[0][n - 1];
  // 時間：O(n³)，空間：O(n²)
}

console.log(maxCoins([3, 1, 5, 8])); // 輸出：167
console.log(maxCoins([1, 5]));        // 輸出：10

function intervalDP(arr: number[]): number {
  const n = arr.length;
  // 初始化 dp 表（長度為 1 的區間通常為 0 或特定基底值）
  const dp: number[][] = Array.from({ length: n }, () => new Array(n).fill(0));

  // 外層枚舉區間長度，從 2 開始（長度 1 為基底）
  for (let len = 2; len <= n; len++) {
    for (let l = 0; l + len - 1 < n; l++) {
      const r = l + len - 1;
      dp[l][r] = Infinity;
      // 枚舉分割點 k：將 [l, r] 分成 [l, k] 和 [k+1, r]
      for (let k = l; k < r; k++) {
        const cost = arr[l] + arr[k] + arr[r]; // 根據題目替換
        dp[l][r] = Math.min(dp[l][r], dp[l][k] + dp[k + 1][r] + cost);
      }
    }
  }

  return dp[0][n - 1];
}

function tsp(dist: number[][]): number {
  const n = dist.length;
  const full = (1 << n) - 1; // 所有城市都訪問過的 mask

  // dp[mask][i] = 已訪問 mask 中的城市，當前在城市 i 的最短距離
  // 初始化為 Infinity
  const INF = 1e9;
  const dp: number[][] = Array.from(
    { length: 1 << n },
    () => new Array(n).fill(INF)
  );

  // 起點：從城市 0 出發，mask 為 0b...0001
  dp[1][0] = 0;

  for (let mask = 1; mask <= full; mask++) {
    for (let u = 0; u < n; u++) {
      // 城市 u 必須在 mask 中
      if (!(mask & (1 << u))) continue;
      if (dp[mask][u] === INF) continue;

      // 嘗試前往未訪問的城市 v
      for (let v = 0; v < n; v++) {
        if (mask & (1 << v)) continue; // v 已訪問，跳過
        const nextMask = mask | (1 << v);
        dp[nextMask][v] = Math.min(dp[nextMask][v], dp[mask][u] + dist[u][v]);
      }
    }
  }

  // 計算回到起點 0 的最短路徑
  let ans = INF;
  for (let u = 1; u < n; u++) {
    if (dist[u][0] < INF) {
      ans = Math.min(ans, dp[full][u] + dist[u][0]);
    }
  }

  return ans === INF ? -1 : ans;
  // 時間：O(2^n × n²)，空間：O(2^n × n)
}

// 測試：4 個城市，距離矩陣
const dist = [
  [0, 10, 15, 20],
  [10, 0, 35, 25],
  [15, 35, 0, 30],
  [20, 25, 30, 0],
];
console.log(tsp(dist)); // 輸出：80（路徑：0→1→3→2→0）

function canPartitionKSubsets(nums: number[], k: number): boolean {
  const total = nums.reduce((a, b) => a + b, 0);
  if (total % k !== 0) return false;
  const target = total / k;
  if (nums.some(n => n > target)) return false;

  // 大的先放，剪枝更有效
  nums.sort((a, b) => b - a);
  const n = nums.length;
  const full = (1 << n) - 1;

  // dp[mask] = 已選 mask 中的數字後，當前桶的累積餘數（對 target 取模）
  // -1 表示此狀態不可達
  const dp = new Int32Array(1 << n).fill(-1);
  dp[0] = 0; // 初始狀態：無元素選取

  for (let mask = 0; mask <= full; mask++) {
    if (dp[mask] === -1) continue;
    for (let i = 0; i < n; i++) {
      if (mask & (1 << i)) continue; // 已選，跳過
      const next = mask | (1 << i);
      const cur = dp[mask] + nums[i];
      if (cur <= target) {
        // cur === target 表示一個桶滿了，下一個桶從 0 開始
        dp[next] = cur % target;
      }
    }
  }

  // 所有元素選完，最後一個桶恰好裝滿
  return dp[full] === 0;
  // 時間：O(2^n × n)，空間：O(2^n)
}

console.log(canPartitionKSubsets([4, 3, 2, 3, 5, 2, 1], 4)); // 輸出：true
console.log(canPartitionKSubsets([1, 2, 3, 4], 3));           // 輸出：false

function countSpecialNumbers(n: number): number {
  const digits = String(n).split('').map(Number);
  const len = digits.length;

  // 記憶化：key 為 (pos, usedMask, tight, started) 的組合
  const memo = new Map<string, number>();

  function dfs(pos: number, mask: number, tight: boolean, started: boolean): number {
    // 所有位都填完，若已開始填數字則計數 1，否則 0（防止純前導零）
    if (pos === len) return started ? 1 : 0;

    const key = `${pos},${mask},${tight},${started}`;
    if (memo.has(key)) return memo.get(key)!;

    // tight 決定當前位最多能填幾
    const limit = tight ? digits[pos] : 9;
    let result = 0;

    for (let d = 0; d <= limit; d++) {
      // 已開始填數字且數字 d 已用過，跳過
      if (started && (mask >> d) & 1) continue;

      const newTight = tight && d === limit;      // 是否繼續受上界約束
      const newStarted = started || d !== 0;      // 填入非 0 數字即視為開始
      // 前導零不佔用數字名額（007 中前兩個 0 不算「用過 0」）
      const newMask = newStarted ? mask | (1 << d) : mask;

      result += dfs(pos + 1, newMask, newTight, newStarted);
    }

    memo.set(key, result);
    return result;
  }

  return dfs(0, 0, true, false);
  // 時間：O(10 × 2^10 × len)，空間：O(2^10 × len)
}

console.log(countSpecialNumbers(20));  // 輸出：19
console.log(countSpecialNumbers(135)); // 輸出：110

function countWithoutFour(n: number): number {
  const digits = String(n).split('').map(Number);
  const len = digits.length;
  // memo[pos][tight] 即可記憶化（此題狀態較簡單）
  const memo: Map<string, number> = new Map();

  function dfs(pos: number, tight: boolean, started: boolean): number {
    if (pos === len) return started ? 1 : 0;

    const key = `${pos},${tight},${started}`;
    if (memo.has(key)) return memo.get(key)!;

    const limit = tight ? digits[pos] : 9;
    let result = 0;

    for (let d = 0; d <= limit; d++) {
      if (d === 4) continue; // 跳過含有數字 4 的選擇
      if (!started && d === 0) {
        // 前導零：繼續但不視為開始
        result += dfs(pos + 1, false, false);
      } else {
        result += dfs(pos + 1, tight && d === limit, true);
      }
    }

    memo.set(key, result);
    return result;
  }

  return dfs(0, true, false);
}

console.log(countWithoutFour(100)); // 輸出：72（1-100 中不含 4 的數）

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int maxCoins(vector<int>& nums) {
        int n = nums.size();
        // 在兩端插入虛擬氣球 1
        vector<int> arr;
        arr.push_back(1);
        for (int x : nums) arr.push_back(x);
        arr.push_back(1);
        int m = arr.size();

        // dp[l][r] = 戳破開區間 (l, r) 內所有氣球的最大硬幣
        vector<vector<int>> dp(m, vector<int>(m, 0));

        for (int len = 2; len < m; len++) {
            for (int l = 0; l + len < m; l++) {
                int r = l + len;
                for (int k = l + 1; k < r; k++) {
                    int coins = arr[l] * arr[k] * arr[r];
                    dp[l][r] = max(dp[l][r], dp[l][k] + coins + dp[k][r]);
                }
            }
        }
        return dp[0][m - 1];
    }
};

#include <vector>
#include <climits>
#include <algorithm>
using namespace std;

int tsp(vector<vector<int>>& dist) {
    int n = dist.size();
    int full = (1 << n) - 1;
    const int INF = INT_MAX / 2;

    // dp[mask][i] = 已訪問 mask 中城市，當前在城市 i 的最短距離
    vector<vector<int>> dp(1 << n, vector<int>(n, INF));
    dp[1][0] = 0; // 從城市 0 出發

    for (int mask = 1; mask <= full; mask++) {
        for (int u = 0; u < n; u++) {
            if (!(mask & (1 << u))) continue;
            if (dp[mask][u] == INF) continue;
            for (int v = 0; v < n; v++) {
                if (mask & (1 << v)) continue;
                int nextMask = mask | (1 << v);
                dp[nextMask][v] = min(dp[nextMask][v], dp[mask][u] + dist[u][v]);
            }
        }
    }

    int ans = INF;
    for (int u = 1; u < n; u++) {
        if (dist[u][0] != INF)
            ans = min(ans, dp[full][u] + dist[u][0]);
    }
    return ans == INF ? -1 : ans;
}

// C++ 位元操作小技巧（GCC/Clang 內建）：
// __builtin_popcount(mask)  → mask 中 1 的個數（已選元素數）
// __builtin_ctz(mask)       → 末尾 0 的個數（最低位 1 的位置）
// 例：__builtin_popcount(0b1101) = 3
//     __builtin_ctz(0b1100)      = 2

#include <string>
#include <vector>
#include <functional>
using namespace std;

int countSpecialNumbers(int n) {
    string s = to_string(n);
    int len = s.size();

    // memo[pos][mask][tight][started]
    vector<vector<vector<vector<int>>>> memo(
        len,
        vector<vector<vector<int>>>(
            1 << 10,
            vector<vector<int>>(2, vector<int>(2, -1))
        )
    );

    function<int(int, int, bool, bool)> dfs =
        [&](int pos, int mask, bool tight, bool started) -> int {
        if (pos == len) return started ? 1 : 0;

        auto& ref = memo[pos][mask][tight][started];
        if (ref != -1) return ref;

        int limit = tight ? (s[pos] - '0') : 9;
        int result = 0;

        for (int d = 0; d <= limit; d++) {
            if (started && (mask >> d & 1)) continue;
            bool newTight = tight && (d == limit);
            bool newStarted = started || (d != 0);
            int newMask = newStarted ? (mask | (1 << d)) : mask;
            result += dfs(pos + 1, newMask, newTight, newStarted);
        }

        return ref = result;
    };

    return dfs(0, 0, true, false);
}

/**
 * LCS 空間優化版：O(m × n) → O(min(m, n))
 * 每次只保留「前一行」的值
 */
function lcSpaceOptimized(text1: string, text2: string): number {
  // 確保 text2 是較短的字串（最小化空間）
  if (text1.length < text2.length) [text1, text2] = [text2, text1];
  const m = text1.length, n = text2.length;

  let prev = new Array<number>(n + 1).fill(0);
  let curr = new Array<number>(n + 1).fill(0);

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (text1[i - 1] === text2[j - 1]) {
        curr[j] = prev[j - 1] + 1;
      } else {
        curr[j] = Math.max(prev[j], curr[j - 1]);
      }
    }
    // 滾動交換：讓 curr 成為下一輪的 prev
    [prev, curr] = [curr, prev];
    curr.fill(0);
  }

  return prev[n];
}

console.log(lcSpaceOptimized("abcde", "ace")); // 輸出：3

/**
 * 滑動視窗最小值 DP（單調佇列優化）
 * dp[i] = min(dp[j]) + nums[i]，j 在 [i-k, i-1] 範圍內
 * Time: O(n)，Space: O(n)
 */
function slidingWindowMinDP(nums: number[], k: number): number {
  const n = nums.length;
  const dp = new Array(n).fill(Infinity);
  dp[0] = 0;
  // 單調遞增佇列，存放索引，佇列頭部是視窗內 dp 值最小的索引
  const deque: number[] = [0];

  for (let i = 1; i < n; i++) {
    // 移除過期元素（超出視窗 [i-k, i-1]）
    while (deque.length > 0 && deque[0] < i - k) deque.shift();

    // 用佇列頭部（最小值）更新 dp[i]
    if (deque.length > 0) {
      dp[i] = dp[deque[0]] + nums[i];
    }

    // 維護單調遞增性：隊尾 dp 值 >= dp[i] 時移除
    // 因為 i 比隊尾更新且值更小，隊尾永遠不會被選到
    while (deque.length > 0 && dp[deque[deque.length - 1]] >= dp[i]) {
      deque.pop();
    }
    deque.push(i);
  }

  return dp[n - 1];
}

/**
 * 0/1 背包空間優化演示
 * 二維版：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w]+v)
 * 壓縮後：dp[j] = max(dp[j], dp[j-w]+v)
 * 從右往左遍歷：保證 dp[j-w] 是上一輪（未選當前物品）的值
 */
function knapsack01(weights: number[], values: number[], capacity: number): number {
  const dp = new Array<number>(capacity + 1).fill(0);

  for (let i = 0; i < weights.length; i++) {
    // 從右往左：確保 dp[j-weights[i]] 尚未被當輪更新
    for (let j = capacity; j >= weights[i]; j--) {
      dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
    }
  }

  return dp[capacity];
}