一、學習目標

• 把題目抽象成 dp[l][r]：表示處理區間 [l..r] 的最佳值/最少代價。
• 會寫兩大形態的轉移：
  • 兩端取數：dp[l][r] 來自 dp[l+1][r] 或 dp[l][r-1]（遊戲、取端點）。
  • 「最後一次切點」/「最後一個保留」：枚舉 k 將區間分成兩半，或把 k 當作區間內最後被處理的元素。
• 正確的迭代順序：按區間長度 len = 1..n 擴大；每次用到的更短區間已經計好。
• 熟悉常見加速/心法：前綴和（快速算區間和）。

二、觀念說明

為什麼用 dp[l][r]？

許多問題都可拆成「先把內部子區間解完，再處理邊界/中間某一步」的型態。
常見三種模式：

• 兩端取數（遊戲）：玩家每次從左或右取一個；dp[l][r] 依賴 dp[l+1][r] / dp[l][r-1]。
• 最後一次切/合併：像矩陣連乘、多邊形三角剖分，dp[l][r] = min_k dp[l][k] + dp[k+1][r] + cost(l,k,r)。
• 最後一個保留（或最後一個擊破）：像 Burst Balloons，dp[l][r] 取「在 (l,r) 之間選一個 k 當最後處理」，好處是 k 左右的子問題互不干擾。

迭代順序

• 外層 for (len = 1..n)，內層枚舉 l，令 r = l + len - 1。
• 長度 1 的 base（單字元、單元素）通常容易決定；再用它們堆出長度 2、3… 的解。

前綴和與型別

• 只要跟區間和有關（如遊戲總分），先建 prefix[i] = a[0..i-1]，sum(l,r)=prefix[r+1]-prefix[l]。
• 金額/方法數常要 long long；CSES 幾乎不可用 int64 關鍵字（請用 long long）。

常見陷阱

• 區間邊界（l+1、r-1）越界；長度條件沒守好。
• 忘了用嚴格的迭代順序（導致用到未被計算的狀態）。
• 記憶體：n=5000 時 long long dp[5000][5000] 約 200MB，可行但偏大；能 1D 就 1D。

三、CSES實戰演練

題目1:Removal Game

原題:
https://cses.fi/problemset/task/1097

題意:
有長度 n 的數列，兩人輪流從左或右端取一個數，加到自己的分數。雙方最佳策略，問先手最多拿多少分。

解題思路:

• 定義 dp[l][r] = 先手 − 後手 在 [l..r] 上的分差最大值。
• 轉移：
  • dp[l][r] = max( a[l] - dp[l+1][r], a[r] - dp[l][r-1] )
  • 最後先手實際分數 = (sum(a) + dp[0][n-1]) / 2。
• 用 1 維滾動把 dp[i][j] 壓成 dp[i]（從短區間往長區間推）。

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

int main() {
    int n;
    cin >> n;
    vector<long long> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];

    // dp[l] 代表當前區間長度下的 dp[l][r]（先手-後手的最大分差）
    vector<long long> dp(n, 0);
    for (int i = 0; i < n; ++i) dp[i] = a[i]; // len=1

    for (int len = 2; len <= n; ++len) {
        for (int l = 0; l + len - 1 < n; ++l) {
            int r = l + len - 1;
            long long takeL = a[l] - dp[l + 1]; // 取左，對手面對 [l+1..r]
            long long takeR = a[r] - dp[l];     // 取右，對手面對 [l..r-1]
            dp[l] = (takeL > takeR) ? takeL : takeR;
        }
    }

    long long total = 0;
    for (int i = 0; i < n; ++i) total += a[i];
    long long first = (total + dp[0]) / 2; // 先手實際分數
    cout << first << '\n';
    return 0;
}

題目2:Rectangle Cutting

原題:
https://cses.fi/problemset/task/1744

題意:
給長方形大小 a × b，每次只能沿格線作整條直切，問最少需要切幾刀才能把它切成若干個正方形。

解題思路:

• 狀態：dp[x][y] = 把 x × y 切成正方形的最少刀數。
• 初值：若 x == y，已是正方形，dp[x][y] = 0。
• 轉移：枚舉一次水平切或垂直切的位置：
  • 水平：對 i = 1..x-1，dp[x][y] = min(dp[x][y], dp[i][y] + dp[x-i][y] + 1);
  • 垂直：對 j = 1..y-1，dp[x][y] = min(dp[x][y], dp[x][j] + dp[x][y-j] + 1);
• 迭代順序：從小矩形往大矩形填表即可。為了省一半計算，可用對稱性 dp[x][y] == dp[y][x]。

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

int main() {
    int a, b;
    cin >> a >> b;

    // dp[x][y] = x*y 矩形切成正方形的最少刀數
    vector<vector<int> > dp(a + 1, vector<int>(b + 1, 0));

    for (int x = 1; x <= a; ++x) {
        for (int y = 1; y <= b; ++y) {
            if (x == y) { dp[x][y] = 0; continue; }
            int best = INT_MAX / 4;

            // 水平切成 i 和 x-i
            for (int i = 1; i < x; ++i) {
                int cand = dp[i][y] + dp[x - i][y] + 1;
                if (cand < best) best = cand;
            }
            // 垂直切成 j 和 y-j
            for (int j = 1; j < y; ++j) {
                int cand = dp[x][j] + dp[x][y - j] + 1;
                if (cand < best) best = cand;
            }
            dp[x][y] = best;
        }
    }
    cout << dp[a][b] << '\n';
    return 0;
}

四、Leetcode實戰演練

題目1:Longest Palindromic Subsequence

原題:
https://leetcode.com/problems/longest-palindromic-subsequence/

題意:
給字串 s，回傳其最長回文子序列（不必連續）的長度。

解題思路:

• 狀態：dp[l][r] = s[l..r] 的最長回文子序列長度。
• 轉移：
  • 若 s[l]==s[r]：dp[l][r] = dp[l+1][r-1] + 2（或當區間長度≤2時設為 2）。
  • 否則 dp[l][r] = max(dp[l+1][r], dp[l][r-1])。
• 迭代：依區間長度 len = 1..n 擴大；dp[i][i]=1。

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n = (int)s.size();
        if (n == 0) return 0;
        static int dp[1005][1005]; // n ≤ 1000 可；更大可改用 vector
        for (int i = 0; i < n; ++i) dp[i][i] = 1;

        for (int len = 2; len <= n; ++len) {
            for (int l = 0; l + len - 1 < n; ++l) {
                int r = l + len - 1;
                if (s[l] == s[r]) {
                    dp[l][r] = (l + 1 <= r - 1) ? dp[l + 1][r - 1] + 2 : 2;
                } else {
                    dp[l][r] = dp[l + 1][r] > dp[l][r - 1] ? dp[l + 1][r] : dp[l][r - 1];
                }
            }
        }
        return dp[0][n - 1];
    }
};

題目2:Palindromic Substrings

原題:
https://leetcode.com/problems/palindromic-substrings/

題意:
回傳字串裡共有多少個回文子串（必須連續）。

解題思路:

• 狀態：dp[l][r] = s[l..r] 是否為回文。
• 轉移：s[l]==s[r] 且 (r-l<=2 或 dp[l+1][r-1]) ⇒ dp[l][r]=true，答案 +1。
• 迭代：依 len=1..n 擴大；長度 1、2 要特判。

class Solution {
public:
    int countSubstrings(string s) {
        int n = (int)s.size();
        if (n == 0) return 0;
        static char dp[1005][1005]; // 用 char 節省空間：0/1
        int ans = 0;

        for (int len = 1; len <= n; ++len) {
            for (int l = 0; l + len - 1 < n; ++l) {
                int r = l + len - 1;
                if (s[l] == s[r]) {
                    if (r - l <= 2) dp[l][r] = 1;                 // 1 或 2 或 3 長度時，頭尾相同即回文
                    else dp[l][r] = dp[l + 1][r - 1];
                } else dp[l][r] = 0;
                if (dp[l][r]) ++ans;
            }
        }
        return ans;
    }
};