leetcode 664. Strange Printer 奇怪的打印机+最小打印次数 + 动态规划DP

浅浅的花香味﹌ 2022-06-03 07:44 145阅读 0赞

There is a strange printer with the following two special requirements:

The printer can only print a sequence of the same character each time.  
At each turn, the printer can print new characters starting from and ending at any places, and will cover the original existing characters.  
Given a string consists of lower English letters only, your job is to count the minimum number of turns the printer needed in order to print it.

Example 1:  
Input: “aaabbb”  
Output: 2  
Explanation: Print “aaa” first and then print “bbb”.  
Example 2:  
Input: “aba”  
Output: 2  
Explanation: Print “aaa” first and then print “b” from the second place of the string, which will cover the existing character ‘a’.  
Hint: Length of the given string will not exceed 100.

对于每个string，考虑最后XXXXX，分成2部分。如果第一部分的最后与第二部分的最后一样（为什么考虑最后一位呢？就是为什么是j-1和i+d呢？因为我们现在求得是i-i+d范围，要么是后半部分开始的j，要么是i+d，试想如果j和j+1是一样的，那么就会在j的下一个循环被考虑到，因此我们只需要考虑后半部分的结尾就可以，当然为了以防万一也可以吧j和j+1相等的情况也写进代码） 那在print第一部分的最后的时候就可以吧第二部分的最后也顺带处理掉了，这时候就要减一 ， 如果不能分成2部分，比如aaaaaa，在减一的时候就处理掉了

参考链接[ 664. Strange Printer][664. Strange Printer]

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    
    using namespace std;
    
    
    class Solution 
    {
    public:
        int strangePrinter(string s) 
        {
            int n = s.length();
            if (n == 0)
                return 0;
            vector<vector<int>> dp(n, vector<int>(n, 0));
            for (int i = 0; i < n; i++)
                dp[i][i] = 1;
    
            for (int len = 1; len <= n; len++)
            {
                for (int i = 0; i + len < n; i++)
                {
                    dp[i][i + len] = len + 1;
                    for (int j = i + 1; j <= i + len; j++)
                    {
                        int t = dp[i][j - 1] + dp[j][i + len];
                        if (s[j - 1] == s[i + len])
                            t--;
                        dp[i][i + len] = min(dp[i][i + len], t);
                    }
                }
            }
            return dp[0][n - 1];
        }
    };

[664. Strange Printer]: http://blog.csdn.net/zjucor/article/details/77430144