problem:664. 奇怪的打印机

思路：定义dp[i][j]为区间打印[i,j]的最少次数，考虑一个简单的s:’aba’，可以发现s[i]==s[j]时候，可以直接两个a可以同时打印，转移到s[i+1][j]或者s[i][j-1]区间，当s[i]！=s[j]时，答案肯定在子区间中，枚举每个子区间即可,dp[i][j] = min(dp[i][j],dp[i,k][k+1][j])

Accode:

class Solution {
public:
    int strangePrinter(string s) {
        int n = s.size();
        // vector<vector<int>> dp(n, vector<int>(n, 0x3f3f3f3f));
        int dp[n][n];
        memset(dp, 0x3f3f3f3f, sizeof(dp));

        for(int i = 0; i < n; i++)
            dp[i][i] = 1;

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

时间复杂度：$o(n^3)$