题目描述
有台奇怪的打印机有以下两个特殊要求:
-
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
}
}
题解太赞了!
妙啊 太棒了
哈哈,谢谢!此题是区间dp合并石子https://www.acwing.com/problem/content/284/ 的应用,有兴趣可以去看看~~