動態規劃基礎 — 五步驟解題法與經典 DP 問題詳解 | 資料結構與演算法

// 方式一：暴力遞迴（O(2^n)，僅示意，n > 40 就超時）
function climbStairsNaive(n: number): number {
  if (n <= 2) return n;
  return climbStairsNaive(n - 1) + climbStairsNaive(n - 2);
}

// 方式二：Top-Down 記憶化（O(n) 時間，O(n) 空間）
function climbStairsMemo(
  n: number,
  memo: Map<number, number> = new Map()
): number {
  if (n <= 2) return n;
  if (memo.has(n)) return memo.get(n)!;
  const result = climbStairsMemo(n - 1, memo) + climbStairsMemo(n - 2, memo);
  memo.set(n, result);
  return result;
}

// 方式三：Bottom-Up + 空間優化（O(n) 時間，O(1) 空間）
function climbStairs(n: number): number {
  if (n <= 2) return n;
  let dp1 = 1, dp2 = 2; // dp[1]=1, dp[2]=2
  for (let i = 3; i <= n; i++) {
    const curr = dp1 + dp2;
    dp1 = dp2;
    dp2 = curr;
  }
  return dp2;
}

console.log(climbStairs(5));  // 輸出：8
console.log(climbStairs(10)); // 輸出：89

/**
 * 0/1 背包問題（一維滾動陣列，空間優化版）
 * Time: O(n × capacity), Space: O(capacity)
 */
function knapsack01(
  weights: number[],
  values: number[],
  capacity: number
): number {
  const n = weights.length;
  // dp[j] = 容量為 j 時能獲得的最大價值
  const dp = new Array<number>(capacity + 1).fill(0);

  for (let i = 0; i < n; 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];
}

// 測試：3 個物品，重量 [2,3,4]，價值 [3,4,5]，背包容量 5
const weights = [2, 3, 4];
const values  = [3, 4, 5];
console.log(knapsack01(weights, values, 5)); // 輸出：7（選物品 0 + 物品 1）

/**
 * 最長共同子序列（Longest Common Subsequence）
 * Time: O(m × n), Space: O(m × n)
 */
function longestCommonSubsequence(text1: string, text2: string): number {
  const m = text1.length, n = text2.length;
  // dp[i][j]：text1 前 i 字元和 text2 前 j 字元的 LCS 長度
  const dp: number[][] = Array.from({ length: m + 1 }, () =>
    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]) {
        // 字元匹配：繼承左上角 + 1
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        // 字元不匹配：取上方或左方的較大值
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }

  return dp[m][n];
}

console.log(longestCommonSubsequence("abcde", "ace")); // 輸出：3（"ace"）
console.log(longestCommonSubsequence("abc", "abc"));   // 輸出：3
console.log(longestCommonSubsequence("abc", "def"));   // 輸出：0

/**
 * 最長遞增子序列（Longest Increasing Subsequence）
 *
 * 方法一：O(n²) 標準 DP
 * 狀態：dp[i] = 以 nums[i] 結尾的最長遞增子序列長度
 * 轉移：dp[i] = max(dp[j] + 1)，對所有 j < i 且 nums[j] < nums[i]
 * 注意：答案是 max(dp)，不是 dp[n-1]！
 */
function lisN2(nums: number[]): number {
  const n = nums.length;
  if (n === 0) return 0;

  const dp = new Array<number>(n).fill(1); // 每個元素自身是長度 1 的 LIS
  let maxLen = 1;

  for (let i = 1; i < n; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[j] < nums[i]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
    maxLen = Math.max(maxLen, dp[i]);
  }

  return maxLen;
}

/**
 * 方法二：O(n log n) — 耐心排序（Patience Sorting）+ 二分搜尋
 * tails[i] = 長度為 i+1 的遞增子序列的最小末尾值
 * tails 始終有序，可用二分搜尋找插入位置
 *
 * 注意：tails 陣列本身不是實際的 LIS，但其長度等於 LIS 長度
 */
function lisNLogN(nums: number[]): number {
  const tails: number[] = [];

  for (const num of nums) {
    // 二分搜尋：找 tails 中第一個 >= num 的位置
    let lo = 0, hi = tails.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (tails[mid] < num) lo = mid + 1;
      else hi = mid;
    }
    // 若 lo === tails.length，代表 num 大於所有元素，擴展 tails
    // 否則替換 tails[lo]（保持最小末尾值，為後續更長子序列留空間）
    tails[lo] = num;
  }

  return tails.length;
}

// 測試：[10, 9, 2, 5, 3, 7, 101, 18]，LIS 為 [2, 3, 7, 18] 或 [2, 5, 7, 101]
console.log(lisN2([10, 9, 2, 5, 3, 7, 101, 18]));    // 輸出：4
console.log(lisNLogN([10, 9, 2, 5, 3, 7, 101, 18])); // 輸出：4

/**
 * 最小路徑和（Minimum Path Sum）
 * 只能向右或向下移動，求左上角到右下角的最小路徑和
 * Time: O(m × n), Space: O(m × n)，可原地修改 grid 降至 O(1)
 */
function minPathSum(grid: number[][]): number {
  const m = grid.length, n = grid[0].length;
  const dp: number[][] = Array.from({ length: m }, () =>
    new Array<number>(n).fill(0)
  );

  // 初始條件：第 0 行（只能從左走）
  dp[0][0] = grid[0][0];
  for (let j = 1; j < n; j++) dp[0][j] = dp[0][j - 1] + grid[0][j];
  // 初始條件：第 0 列（只能從上走）
  for (let i = 1; i < m; i++) dp[i][0] = dp[i - 1][0] + grid[i][0];

  // 填充其餘格子
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      dp[i][j] = grid[i][j] + Math.min(dp[i - 1][j], dp[i][j - 1]);
    }
  }

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

console.log(minPathSum([[1,3,1],[1,5,1],[4,2,1]])); // 輸出：7（1→3→1→1→1）

/**
 * 零錢兌換（Coin Change）— 完全背包變體
 * 每種硬幣可無限次使用，求組成 amount 的最少硬幣數
 * Time: O(amount × coins.length), Space: O(amount)
 */
function coinChange(coins: number[], amount: number): number {
  // 初始化為 amount+1（安全的「不可達」哨兵值，避免 Infinity + 1 溢出）
  const dp = new Array<number>(amount + 1).fill(amount + 1);
  dp[0] = 0;

  for (let i = 1; i <= amount; i++) {
    for (const coin of coins) {
      if (i >= coin) {
        dp[i] = Math.min(dp[i], dp[i - coin] + 1);
      }
    }
  }

  // 若 dp[amount] 仍為哨兵值，代表無法湊出
  return dp[amount] > amount ? -1 : dp[amount];
}

console.log(coinChange([1, 5, 11], 15)); // 輸出：3（5+5+5）
console.log(coinChange([1, 2, 5], 11));  // 輸出：3（5+5+1）
console.log(coinChange([2], 3));         // 輸出：-1（無法湊出）

#include <vector>
#include <algorithm>

/**
 * 0/1 背包 — 二維版本（清晰展示轉移邏輯）
 * Time: O(n*W), Space: O(n*W)
 */
int knapsack2D(const std::vector<int>& weights,
               const std::vector<int>& values,
               int capacity) {
    int n = static_cast<int>(weights.size());
    // dp[i][j]：考慮前 i 個物品、容量為 j 時的最大價值
    std::vector<std::vector<int>> dp(n + 1, std::vector<int>(capacity + 1, 0));

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= capacity; j++) {
            dp[i][j] = dp[i - 1][j]; // 不選第 i 個物品
            if (j >= weights[i - 1]) {
                dp[i][j] = std::max(dp[i][j],
                    dp[i - 1][j - weights[i - 1]] + values[i - 1]);
            }
        }
    }
    return dp[n][capacity];
}

/**
 * 0/1 背包 — 一維滾動陣列（空間優化）
 * Time: O(n*W), Space: O(W)
 * 關鍵：內層必須從右往左，確保每個物品只選一次
 */
int knapsack1D(const std::vector<int>& weights,
               const std::vector<int>& values,
               int capacity) {
    std::vector<int> dp(capacity + 1, 0);

    for (int i = 0; i < static_cast<int>(weights.size()); i++) {
        for (int j = capacity; j >= weights[i]; j--) {
            dp[j] = std::max(dp[j], dp[j - weights[i]] + values[i]);
        }
    }
    return dp[capacity];
}

#include <vector>
#include <algorithm>

/**
 * LIS — O(n log n)，使用 STL lower_bound 二分搜尋
 * lower_bound 找第一個 >= num 的位置
 */
int lisOptimal(const std::vector<int>& nums) {
    std::vector<int> tails;

    for (int num : nums) {
        auto it = std::lower_bound(tails.begin(), tails.end(), num);
        if (it == tails.end()) {
            tails.push_back(num); // num 最大，擴展 tails
        } else {
            *it = num; // 替換，維持最小末尾值
        }
    }
    return static_cast<int>(tails.size());
}

#include <vector>
#include <algorithm>

/**
 * Coin Change — 完全背包
 * 初始化為 amount+1 而非 INT_MAX，避免 INT_MAX + 1 整數溢出
 * Time: O(amount × coins.size()), Space: O(amount)
 */
int coinChange(const std::vector<int>& coins, int amount) {
    std::vector<int> dp(amount + 1, amount + 1);
    dp[0] = 0;

    for (int i = 1; i <= amount; i++) {
        for (int coin : coins) {
            if (i >= coin) {
                dp[i] = std::min(dp[i], dp[i - coin] + 1);
            }
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
}

/**
 * 完全背包（零錢兌換是其最大化版本，此為最大化價值版）
 * 內層從左往右：允許同一物品重複選取
 */
function unboundedKnapsack(
  weights: number[],
  values: number[],
  capacity: number
): number {
  const dp = new Array<number>(capacity + 1).fill(0);

  for (let i = 0; i < weights.length; i++) {
    // 從左往右！與 0/1 背包的關鍵區別
    for (let j = weights[i]; j <= capacity; j++) {
      dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
    }
  }

  return dp[capacity];
}

/**
 * LCS 空間優化版：O(m*n) → O(min(m, n))
 * 每次只保留「前一行」的 dp 值
 */
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]);
      }
    }
    [prev, curr] = [curr, prev]; // 滾動交換，避免額外記憶體分配
    curr.fill(0);
  }

  return prev[n];
}

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