Hard
Related Topics: String / Dynamic Programming
LeetCode Source

解題想法

這道題目是關於計算最少打印次數以形成給定字串 s。

我們利用動態規劃（Dynamic Programming, DP）來解決這個問題。

首先，我們定義 dp[i][j] 為將子字串 s[i:j+1] 打印出來所需的最少次數。

接著，我們從右到左開始遍歷字串，以確保在計算時可以利用之前計算的結果。

當 i 和 j 相等時，dp[i][i] 顯然為 1，因為只需打印一次即可。

對於 j > i 的情況，我們可以先假設將字串 s[i:j+1] 以 dp[i][j-1] + 1 來打印，因為新增一個字母會增加一次打印次數。

然而，如果 s[j] 與某個位置 k 的字母相同，我們可以考慮將 s[k+1:j] 包含在之前的打印過程中，這樣就不需要額外增加打印次數，進而更新 dp[i][j] 的值。

最後，我們的目標是計算 dp[0][l-1]，也就是將整個字串 s 打印出來所需的最少次數。

Complexity

Time Complexity: O(n^3)
Space Complexity: O(n^2)

Python

class Solution:
    def strangePrinter(self, s: str) -> int:
        l = len(s)
        dp = [[0]*l for _ in range(l)]

        for i in range(l-1, -1, -1):
            dp[i][i] = 1
            for j in range(i+1, l):
                dp[i][j] = dp[i][j-1] + 1
                for k in range(i, j):
                    if s[j] == s[k]:
                        a = 0
                        if k+1 <= j-1:
                            a = dp[k+1][j-1]
                        dp[i][j] = min(dp[i][j], dp[i][k] + a)
        return dp[0][l-1]

C++

class Solution {
public:
    int strangePrinter(string s) {
        int l = s.length();
        vector<vector<int>> dp(l, vector<int>(l, 0));

        for (int i = l-1; i >= 0; --i) {
            dp[i][i] = 1;
            for (int j = i+1; j < l; ++j) {
                dp[i][j] = dp[i][j-1] + 1;
                for (int k = i; k < j; ++k) {
                    if (s[j] == s[k]) {
                        int a = 0;
                        if (k+1 <= j-1) {
                            a = dp[k+1][j-1];
                        }
                        dp[i][j] = min(dp[i][j], dp[i][k] + a);
                    }
                }
            }
        }
        return dp[0][l-1];
    }
};