leetcode-664-奇怪的打印机

奇怪的打印机

题面

leetcode题目

有台奇怪的打印机有以下两个特殊要求：
打印机每次只能打印由 同一个字符 组成的序列。
每次可以在任意起始和结束位置打印新字符，并且会覆盖掉原来已有的字符。
给你一个字符串 s ，你的任务是计算这个打印机打印它需要的最少打印次数。

example

输入：s = "aaabbb"
输出：2
解释：首先打印 "aaa" 然后打印 "bbb"。

题解

总体思路

动态规划，推出方程还挺好写的。

解题思路

首先考虑，打印机是连续打印一串字符串的，所以如果是连续的一串，那么一次就能打印结束。
那么显然的，我们也能想到，一串字符串如果\(s[i]\)和\(s[j]\)处相同，那么如果我们需要打印\(s[i]\)，不如直接从\(s[i]\)往\(s[j]\)处连续打印， 这样显然是最优的，不需要额外的步数的同时减少了一个需要打印的字符。
于是我们可以得到\[ dp[i][j] = d[i][j-1] s[i] = s[j] \]
于是我们只需要考虑当\(s[i] \neq s[j]\)时的情况，我们考虑将这串字符串拆成两串处理(大拆小是常见的想法，因为总存在一个基准状态是必然有解的)： \[ dp[i][j] = min_{k=i}^{j-1}(dp[i][k] + dp[k+1][j])，s[i] \neq s[j] \] 显然，存在基础解 \[ dp[i][i] = 1 \] 因为长度为1的串显然只需要键入一次。
由状态转移方程我们可以看出，计算\(dp[i][j]\)的解需要知道\(dp[m][n]\), 其中\[m,n\in \{i,i+1,i+2 \cdots j\} \]的所有值。 我们只知道一组基础解，所以我们需要从小到大的去推导所有值。这也是常见的思路，迭代计算的数组长度。

代码

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <cstring>
using namespace std;

#define _DEBUG
class Solution
{
public:
    int strangePrinter(string s)
    {
        int len = s.length();
        int dp[len][len];
        for (int i = 0; i < len; i++)
        {
            dp[i][i] = 1;
        }
        for (int subLen = 1; subLen < len; subLen++)
        {
            for (int i = len - 1; i >= 0; i--)
            {
                int j = i + subLen;
                if (j >= len)
                {
                    continue;
                }
                if (s[i] == s[j])
                {
                    dp[i][j] = dp[i][j - 1];
                    continue;
                }
                int min = 99999999;
                for (int k = i; k < j; k++)
                {
                    int a = dp[i][k] + dp[k + 1][j];
                    if (a < min)
                    {
                        min = a;
                    }
                }
                dp[i][j] = min;
            }
        }
        return dp[0][len - 1];
    }
};

// for test
int main()
{
    Solution s;
    cout << s.strangePrinter(string("tbgtgb")) << endl;

    return 0;
}