664. Strange Printer

思路：很显然，使用DP算法，过程如下：
1.dp[i][i] = 1
2.dp[i][i+1] = 1 if s[i] == s[i+1]
or
dp[i][i+1] = 2 if s[i] != s[i+1]
3.以此类推，dp[j][i] = min(dp[j][k]+dp[k+1][i]) k在j,i之间
NOTE:如果s[i] == s[j] dp[j][i]要减一哦
4.输出 dp[0][n-1]
细节：需要三层循环：
因为k的取值范围关系，因此j是从i-1开始递减到0的，而k则是递增

class Solution {
public:
    int strangePrinter(string s) {
        if(n<2)return n;
        vector<vector<int>> dp(n,vector<int>(n,INT_MAX));
        dp[0][0] = 1;
        for(int i =1;i<n;i++)
        {
            dp[i][i] = 1;
            dp[i-1][i] = s[i-1]==s[i]?1:2;
            for(int j = i-2;j>-1;j--)
            {
                for(int k = j;k<i;k++){
                    dp[j][i] = min(dp[j][i],dp[j][k]+dp[k+1][i]);
                    }
            if(s[i] == s[j])
                dp[j][i] --;
            }
            
        }
        return dp[0][n-1];
    }
};