题目描述

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

• 1.打印机每次只能打印同一个字符序列。

• 2.每次可以在任意起始和结束位置打印新字符，并且会覆盖掉原来已有的字符。

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

样例

示例 1:

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

示例 1:

输入: "aba"
输出: 2
解释: 首先打印 "aaa" 然后在第二个位置打印 "b" 覆盖掉原来的字符 'a'。
提示: 输入字符串的长度不会超过 100。

算法1

状态表示

集合：f[L,R]代表所有将[L,R]染成最终样子的方式的集合
属性：f[L,R]的值等于该集合的染成最终样子的最少次数

状态表示(只用到长度比它小的状态)

将f[L,R]划分子集，其子集有如下情况：

• f[L,L]的集合,最少次数为f[L + 1,R]+1

• f[L,L + 1]的集合，若s[L + 1] == s[L],则最少次数为f[L,L] + f[L + 2,R]
  否则最少次数为f[L,L + 1] + f[L + 2,R]

• f[L,L + 2]的集合，若s[L + 2] == s[L],则最少次数为f[L,L + 1] + f[L + 3,R]
  否则最少次数为f[L,L + 2] + f[L + 3,R]

• …

• f[L,k]的集合，若s[k] == s[L],则最少次数为f[L,k - 1] + f[k + 1,R]
  否则最少次数为f[L,k] + f[k + 1,R]，其中k属于[L + 1,R]
  注意：当k = R 时，此处会出现f[R + 1,R]的情况，此值为0

注意：此处如果s[k] != s[L]时，即使把该s[k]染成s[L]的颜色，到后面还是会被覆盖，因此
f[L,k] + f[k + 1,R]一定会比其他情况大，所以可以舍去

时间复杂度 $O(n^3)$

Java 代码

class Solution {
    public int strangePrinter(String s) {
        if(s.length() == 0) return 0;
        int n =  s.length();
        int[][] f = new int[n + 1][n + 1];
        //所有要用到的状态都已经算出来，按照长度从小到大枚举
        for(int len = 1;len <= n;len ++)
        {
            for(int L = 0;L + len - 1 < n;L++)
            {
                int R = L + len - 1;
                //第一种情况
                f[L][R] = f[L + 1][R] + 1;
                //其他情况
                for(int k = L + 1;k <= R;k++)
                    if(s.charAt(k) == s.charAt(L))
                        f[L][R] = Math.min(f[L][R], f[L][k - 1] + f[k + 1][R]);
                    else f[L][R] = Math.min(f[L][R], f[L][k] + f[k + 1][R]);//可以省去这行
            }
        }
        return f[0][n - 1];
    }
}

有一道与之与曲同工之处的题目（矩阵连乘问题）

题目描述

矩阵连乘问题描述：给定n个矩阵｛A1, A2, …, An｝，Ai的维数为p[i-1]×p[i]，A[i]与A[i+1]是可乘的，i=1,2 ,…,n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。

算法分析

问：两个矩阵A1×A2相乘需要进行多少次乘法？
答：p × r × t 次
分析：
其中矩阵A1表示为p×q，矩阵A2表示为q×t
一行一列相乘 --> r 次乘法
p 行一列相乘 --> p × r 次乘法
p 行 t 列相乘 -- > p × r × t 次乘法

例如，三个矩阵连乘总共有两种加括号的方式：
      ((A1A2 )A3) 、  (A1(A2 A3))
其数乘次数分别为：7500, 75000。

状态表示

集合：f[L,R]代表所有将[L,R]进行完全加括号得到最终结果的方式的集合
属性：f[L,R]的值等于该集合的乘法数量最少次数

状态表示(只用到长度比它小的状态)

将f[L,R]划分子集，其子集有如下情况：

• f[L,L]的集合,最少次数为f[L + 1,R]+p[L - 1] * p[L] * p[R]

• f[L,L + 1]的集合，最少次数为f[L,L + 1] + p[L - 1] * p[L + 1] * p[R] + f[L + 2,R]

• f[L,L + 2]的集合，最少次数为f[L,L + 2] + p[L - 1] * p[L + 2] * p[R] + f[L + 3,R]

• …

• f[L,k]的集合，最少次数为f[L][k] + p[L - 1] * p[k] * p[R] + f[k + 1][R]，其中k属于[L + 1,R]

时间复杂度 $O(n^3)$

Java 代码

public class 矩阵连乘 {
    //传进一个p[]数组,pi表示Ai的纵坐标
    public static int Matrix(int[] p) {
        int n =  p.length - 1;
        if(p.length == 2) return 0;
        int[][] f = new int[n + 2][n + 2];
        //所有要用到的状态都已经算出来，按照长度从小到大枚举
        for(int len = 2;len <= n;len ++)
        {
            for(int L = 1;L + len - 1 <= n;L++)
            {
                int R = L + len - 1;
                //第一种情况
                f[L][R] = f[L + 1][R] + p[L - 1] * p[L] * p[R];
                //其他情况
                for(int k = L + 1;k <= R;k++)
                    f[L][R] = Math.min(f[L][R], f[L][k] + p[L - 1] * p[k] * p[R] + f[k + 1][R]);

            }
        }
        return f[1][n];
    }
    public static void main(String[] args) {
        // TODO 自动生成的方法存根
        int[] p = new int[] {30,35,15,5,10,20,25};
        int a = Matrix(p);
        System.out.println(a);
        //输出15125
    }
}