博客

1100 奇怪的打印机

有一个奇怪的打印机，它有如下两个特别的要求：

1.这个打印机只每次能打印一个由相同字母构成的串。

2. 在每一轮当中，这个打印机可以打印从任意位置开始到任意位置结束的新字母，并且可以覆盖掉原来存在的字母。给定一个仅包含小写英文字母的字符串，你的任务是计算打印机为了打印出它锁需要的最小轮数。

样例

样例 1:

输入: “aaabbb”

输出: 2

解释: 首先打印 “aaa”，然后打印 “bbb”.

样例 2:

输入: “aba”

输出: 2

解释: 首先打印 “aaa”，然后从字符串的第二个位置开始打印 “b”，覆盖掉原来存在的字母’a’.

注意事项

给定的字符串长度不会超过100。

public class Solution {
    /**
     * @param s: 
     * @return: the minimum number of turns the printer needed in order to print it
     */
    int[][] printer;
    public int strangePrinter(String s) {
        // write your code here
        int len = s.length();
        printer = new int[len][len];
        return dp(s,0,len-1);
    }
    
    public int dp(String s,int i,int j){
        if (i>j){
            return 0;
        } 
        if(printer[i][j] == 0){
            int ans = dp(s , i+1 ,j) + 1;
            for (int k = i+1;k<=j ;++k ) {
                if(s.charAt(i)==s.charAt(k)){
                    ans = Math.min(ans,dp(s,i,k-1)+dp(s,k+1,j));
                }
            }
            printer[i][j] = ans;
        }
        return printer[i][j];
    }
}