dynamicProgramming9

发表于 分类于 ，

题目描述[原题链接][https://leetcode-cn.com/problems/strange-printer/]

有台奇怪的打印机有以下两个特殊要求：

  1. 打印机每次只能打印同一个字符序列。
  2. 每次可以在任意起始和结束位置打印新字符，并且会覆盖掉原来已有的字符。

给定一个只包含小写英文字母的字符串，你的任务是计算这个打印机打印它需要的最少次数。

示例 1:

1
2
3
输入: "aaabbb"
输出: 2
解释: 首先打印 "aaa" 然后打印 "bbb"。

示例 2:

1
2
3
输入: "aba"
输出: 2
解释: 首先打印 "aaa" 然后在第二个位置打印 "b" 覆盖掉原来的字符 'a'。

提示: 输入字符串的长度不会超过 100。

算法描述

区间dp

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int strangePrinter(string s) {
        int n = s.length();
        if(n == 0)return 0;
        int dp[n][n];
        memset(dp,0,n*n*sizeof(int));
        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++){
                int j = i+len;
                dp[i][j] = 1+dp[i+1][j];
                for(int k = i+1;k<j;k++)
                    if(s[i] == s[k])
                        dp[i][j] = min(dp[i][j],dp[i][k-1]+dp[k+1][j]);
                if(s[i]==s[j])
                    dp[i][j] = min(dp[i][j],dp[i+1][j]);
            }
        }
        return dp[0][n-1];
    }
};