題目網址：https://leetcode.cn/problems/palindrome-partitioning-iii/

題意：給一由小寫字母組成的 string s, 和一整數 k。

請按下面的要求分割 s：

  • 首先, 你可以將 s 中的部分 char 修改為其他的小寫英文字母
  • 接著, 你需要把 s 分割成 k 個非空且不相交的 substring, 並且每個 substring 都是回文

返回以這種方式分割 s 所需修改的最少 char 數目。

Solution 1：

想法：利用 DP

1. 定義狀態：

  • 首先, 會在 s 前先加上一個 #, 代表什麼元素都沒有的狀態
  • dp[i][k]：s[1:i] 切割成 k 個回文 substring 的最少修改數

2. 得到轉移方程：

  • dp[i][k] = min(dp[i][k], dp[j - 1][k - 1] + helper(s, j, i)), for 1 ≤ j ≤ i
  • j 初始化成 k 而非 1, 是因為 dp[j - 1][k - 1] 指 nums[1:(j-1)] 拆成 k - 1 個 subarray, 而每個 subarray 至少一個數（j 如果太小, nums[1:(j-1)] 是沒辦法拆成 k - 1 個 subarray 的）
    ➔ 故 j 前面至少 k - 1 個數, 所以 j 的 index 可從 k 開始算

3. 初始化：

  • dp[0][0]：當 s = "" 時, 切割成 0 個回文 substring 的最少修改數為 0
    ➔ dp[0][0] = 0
  • dp[i][0]：當 s 不為空時, s 不可能透過修改 char 使得自身可以切割成 0 個回文 substring, 故將 dp[i][0] 設為 INT_MAX / 2 代表不可能。設 INT_MAX / 2 而非 INT_MAX 是為了避免 overflow（題目要求最小, 故初始值要設大）
    ➔ dp[i][0] = INT_MIN / 2, 其中 1 ≤ i ≤ n
  • dp[0][k]：當 s = "" 時, s 不可能透過修改 char 使得自身可以切割成 k 個回文 substring, 故將 dp[0][k] 設為 INT_MAX / 2 代表不可能
    ➔ dp[0][k] = INT_MIN / 2, 其中 1 ≤ k ≤ k_
class Solution {
public:
    int palindromePartition(string s, int k) {
        const int n = s.size();
        int k_ = k;
        vector<vector<int>> dp(n + 1, vector<int>(k + 1, INT_MAX / 2));

        s = '#' + s;
        dp[0][0] = 0;

        for (int i = 1; i <= n; ++i) {
            for (int k = 1; k <= min(i, k_); ++k) {
                for (int j = k; j <= i; ++j) { // j 起始設 k, 因為 j 前面至少要有 k - 1 個數
                    dp[i][k] = min(dp[i][k], dp[j - 1][k - 1] + helper(s, j, i));
                }
            }
        }

        return dp[n][k];
    }

private:
    // 計算將 s[left:right] 變成回文的最小操作數, time complexity = O(n)
    int helper(const string& s, int left, int right){
        int count = 0;
        while (left < right) {
            if (s[left] != s[right]) {
                ++count;
            }

            ++left;
            --right;
        }
        return count;
    }
};
  • time：$O(n^3 \cdot k)$ ➔ for loop
    • $O(n^2 \cdot k)$：i、k、j 所需的時間分別為 $O(n)$、$O(k)$、$O(n)$
    • $O(n)$：helper() 所需的時間
  • space：$O(n \cdot k)$ ➔ dp

Solution 2：

想法：改善 Solution 1, 將 helper() 改成用 DP 計算（區間 2 型）, 藉此優化時間複雜度

1. 定義狀態：

  • 首先, 會在 s 前先加上一個 #, 代表什麼元素都沒有的狀態
  • count[i][j]：s[i:j] 修改成回文所需的最少操作數

2. 得到轉移方程：

  • 若 s[i] == s[j], 則不需修改任何 char
    ➔ count[i][j] = count[i + 1][j - 1]
  • 否則, 需要修改其中一個 char
    ➔ count[i] = count[i + 1][j - 1] + 1

3. 初始化：

  • count[0][0]：當 s = "" 時, 修改成回文所需的最少操作數為 0
    ➔ count[0][0] = 0
  • count[i][i]：當 s[i:j] 中只有一個 char 時, 修改成回文所需的最少操作數為 0
    ➔ count[i][i] = 0
class Solution {
public:
    int palindromePartition(string s, int k) {
        const int n = s.size();
        int k_ = k;
        vector<vector<int>> dp(n + 1, vector<int>(k + 1, INT_MAX / 2));

        s = '#' + s;
        dp[0][0] = 0;

        vector<vector<int>> count(n + 1, vector<int>(n + 1, 0));

        for (int i = 1; i <= n; ++i) {
            count[i][i] = 0;
        }

        for (int len = 2; len <= n; ++len) {
            for (int i = 1; i + len - 1 <= n; ++i) {
                const int j = i + len - 1;

                if (s[i] == s[j]) {
                    count[i][j] = count[i + 1][j - 1];
                } else {
                    count[i][j] = count[i + 1][j - 1] + 1;
                }
            }
        }

        for (int i = 1; i <= n; ++i) {
            for (int k = 1; k <= min(i, k_); ++k) {
                for (int j = k; j <= i; ++j)  { // j 起始設 k, 因為前面至少要有 k - 1 個數
                    dp[i][k] = min(dp[i][k], dp[j - 1][k - 1] + count[j][i]); // j 在 i 前
                }
            }
        }

        return dp[n][k];
    }
};
  • time：$O(n^2 \cdot k)$ ➔ for loop
  • space：$O(n^2 + n \cdot k)$ ➔ count、dp