算法笔记之动态规划——奇怪的打印机

个人认为比较经典的动态规划处理字符串的题目。

LeetCode 664. 奇怪的打印机

题目描述

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

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

给你一个字符串 s ，你的任务是计算这个打印机打印它需要的最少打印次数。

思路分析

本题目是困难级别，即使知道要使用动态规划也很难想到思路。在这里总结一下做此类题的思路。

考虑初始状态：只有一个字符肯定只需要打印一次。

考虑状态转移，dp[i][j] 代表字符串从索引i到索引j需要打印的次数。那么dp[i][j] = min(dp[i][k] + dp[k + 1][j])，其中k=i,i + 1...j-1的中间索引。这个状态转移在很多动态规划题目中都适用，但是不能只使用它，因为没有考虑到i和j位置可以一同打印的情况。根据题目描述，可以知道用一个字符可以一同打印，那么当索引i和j的字符相同时，我们可以先同时打印索引i和j的字符，再修改中间的其他字符。因此可以得到dp[i][j] = dp[i][j - 1]。

Java代码

根据如上分析，即可得到代码(注意代码中i和j的含义和前面的说明不同)：

class Solution {
    public int strangePrinter(String s) {
        int[][] dp = new int[s.length()][s.length()];
        for(int i = 0; i < s.length(); i++) {
            for(int j = 0; j < s.length() - i; j++) {
                if(i == 0) { // 一个字符
                    dp[j][j + i] = 1;
                } else {
                    if(s.charAt(j) == s.charAt(j + i)) {
                        // 两侧字符相等，可以一起打印，中间再替换
                        dp[j][j + i] = dp[j][j + i - 1];
                    } else {
                        int min = Integer.MAX_VALUE;
                        for(int k = j; k < i + j; k++) {
                            int temp = dp[j][k] + dp[k + 1][i + j];
                            if(temp < min) {
                                min = temp;
                            }
                        }
                        dp[j][j + i] = min;
                    }
                }
            }
        }
        return dp[0][s.length() - 1];
    }
}

可以看到一旦掌握了思路，写起来很简单。但是最难的就是想到解题思路，要掌握动态规划状态转移的共同点。