leetcode664 Strange Printer

思路：
有意思的区间dp。
实现：
 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 class Solution
 5 {
 6 public:
 7     int strangePrinter(string s)
 8     {
 9         int n = s.length();
10         if (n == 0) return 0;
11         vector<vector<int>> dp(n, vector<int>(n, 0));
12         for (int i = 0; i < n; i++)
13         {
14             for (int j = i; j < n; j++)
15             {
16                 if (j == i + 1) dp[i][j] = (s[i] == s[j] ? 1 : 2);
17                 else dp[i][j] = j - i + 1;
18             }
19         }
20         for (int i = n - 1; i >= 0; i--)
21         {
22             for (int j = i + 1; j < n; j++)
23             {
24                 for (int k = i; k < j; k++)
25                 {
26                     dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);
27                     if (s[k] == s[j])
28                     {
29                         dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] - 1);
30                     }
31                 }
32             }
33         }
34         return dp[0][n - 1];
35     }
36 };
37 
38 int main()
39 {
40     cout << Solution().strangePrinter("aba") << endl;
41     cout << Solution().strangePrinter("aaabbb") << endl;
42     cout << Solution().strangePrinter("krkdttnyoqwygja") << endl;
43     cout << Solution().strangePrinter("hello") << endl;
44     return 0;
45 }