单序列型动态规划

• state: f[i] 表示前 i 个位置/数字/字符

• function: f[i] = f[j] ...

• initialize: f[0] = ...

• answer: f[n] 一般 answer 是 f[n] 不是 f[n - 1]。

139. Word Break

• state: f[i]表示“前i”个字符能否被完美切分
• function: f[i] = OR{f[j]} 其中 j < i && j + 1 - i is a word
  • OR 运算的意思
  • 假如 j = 0, 1, 3, 5 时满足 j < i && j + 1 - i is a word
  • 那么 f[i] = f[0] || f[1] || f[3] || f[5]
  • 由于是nested for loop，每一个 i 对应很多个 j，也就是对应很多种不同的切分方式，对于每一个 i 来说，只要有一个切分成立，整个切分就是成立的。所以在这个地方我们要用 || 。
• initialize: f[0] = true
• answer: f[n]

这道题有至少三个优化可以做，等到复习的时候再提吧。

public class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        if (s == null || s.length() == 0) return true;

        int n = s.length();
        boolean[] f = new boolean[n + 1];
        f[0] = true;

        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j < i; ++j) {
                String str = s.substring(j, i);
                f[i] = f[i] || f[j] && wordDict.contains(str);
            }
        }
        return f[n];
    }
}

Word Break这题出现频率也不算低了，常见的follow-up：

• 原题问的是True/False，改为问切几次可以break？
  • 把切完的词放到list里全部返回，就变成了LC140 Word Break II
  • 最少切几次可以切出完美切割？最多/少切几次可以切出字典里的词？
  • 很像下一道题LC132

132. Palindrome Partitioning II

名不虚传的高频Hard题目，这道题对动态规划的理解和时间空间的设计都提出了较高的要求，这道题的篇幅我会稍微写长一点，但可能分析和最终答案都不是最好的，凑合看吧。

• state: f[i]表示前i个字符组成的子串能被分割为最少多少个回文串
• function: f[i] = MIN{f[j] + 1}, j < i && j + 1 - i这一段是一个回文串
• initialize: f[i] = i (f[0] = 0) 空串被切割为0个回文串。
• answer: f[n] – 1
  • 为什么要减一，因为我们定义state的时候是最少分割为多少个回文串，题目问的是最少的切割次数，那么如果我们最少分割为 n 串的话，需要最少切 n - 1 刀。

public class Solution {
    public int minCut(String s) {
        if (s == null || s.length() == 0) return 0;

        int n = s.length();
        int[] f = new int[n + 1];
        f[0] = 0;

        for (int i = 1; i <= n; ++i) {
            f[i] = i;
            for (int j = 0; j < i; ++j) {
                if (valid(s.substring(j, i))) {
                    f[i] = Math.min(f[i], f[j] + 1);
                }
            }
        }
        return f[n] - 1;
    }
    private boolean valid(String s) {
        for (int i = 0; i < s.length(); ++i) {
            int j = s.length() - 1 - i;
            if (s.charAt(i) != s.charAt(j)) return false;
        }
        return true;
    }
}

然而，TLE了

挂在了喜闻乐见的"aaaaaaaaaaa..."case上。

我们原程序其实写的挺傻的，时间复杂度为 O(n^3)。nested for loop是没办法的，因为DP的强项就不是降低时间复杂度的数量级，我们必须想办法从判断valid回文这个地方入手。

冥冥中，耳边回响起了委座的教诲：以空间换时间。张学良表示附议。

所以在这里我们需要对字符串预处理，用一个变量存下valid palindrome的字段。

这就用上了区间型动态规划中valid palindrome的解法。

• State: f[i][j]表示index从i到j这一段是不是一个回文串
• Function: f[i][j] = f[i + 1][j - 1] && (s[i] == s[j])
• Initialize: f[i][i] = true
• Answer: f[x][y] // x, y是你想查询的那一段区间

注意不要越界，注意初始化。

i 依赖于i + 1，算的时候要倒过来，先算大的。本质上是先for区间长度，再for左端点。

这个valid解法和LC125 Valid Palindrome不一样，因为LC125要忽略空格和符号。这个解法其实实战并没有什么优势，只是区间型动态规划的一个例子。

public class Solution {
    public boolean isPalindrome(String s) {
        if (s == null || s.length() == 0) return true;
        int n = s.length();
        boolean[][] f = new boolean[n][n];
        for (int i = 0; i < n; ++i) {
            f[i][i] = true;
        }
        for (int i = 0; i < n - 1; ++i) {
            f[i][i + 1] = (s.charAt(i) == s.charAt(i + 1));
        }
        for (int i = n - 1; i >= 0; --i) {
            for (int j = i + 2; j < n; ++j) {
                f[i][j] = f[i + 1][j - 1] && s.charAt(i) == s.charAt(j);
            }
        }
        return f[0][n - 1];
    }
}

这里你可以直接把整个方法放到前面的代码中做一个预处理，然后拿过来用就行了，很简单的复制粘贴。

但是

写完观察一下，其实我们没必要写一个方法，合二为一就行了，边做valid验证，边进行切割字符串。

不过在这里面，为了适应合二为一的写法，为了迁就valid验证中f[i + 1][j - 1]不越界，让下标统一，我们要修改原来切割state的定义。

• state: f[i]表示切到第i个字母，最少被切割几次可以切割为都是回文串。
• function: f[i] = MIN{f[j - 1] + 1}, charAt(i) == charAt(j) && j - i这一段是一个回文串
• initialize: 不用，因为我们从0开始，边做valid边做切割。
• answer: f[n - 1]

public class Solution {
    public int minCut(String s) {
        if (s == null || s.length() == 0) return 0;

        int n = s.length();
        boolean[][] isPalindrome = new boolean[n][n];
        int[] f = new int[n];

        for(int i = 0; i < n; i++){
            f[i] = i;
            for(int j = 0; j <= i; j++){
                if(s.charAt(i) == s.charAt(j) && (i - j < 2 || isPalindrome[j + 1][i - 1])){
                    isPalindrome[i][j] = isPalindrome[j][i] = true;
                    if(j == 0){
                        f[i] = 0;
                    } else {
                        f[i] = Math.min(f[i], f[j - 1] + 1);
                    }
                }
            }
        }
        return f[n - 1];
    }
}

91. Decode Ways

FB御题。他们就是这么喜欢DP。

思路和climbing stairs没什么区别，就是注意一下以0开头的corner case。

public class Solution {
    public int numDecodings(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int[] f = new int[s.length() + 1];

        f[0] = 1;
        f[1] = s.charAt(0) != '0' ? 1 : 0;

        for (int i = 2; i <= s.length(); ++i) {
            if (s.charAt(i - 1) != '0') {
                f[i] = f[i - 1];
            }
            int twoDigits = (s.charAt(i - 2) - '0') * 10 + s.charAt(i - 1) - '0';
            if (twoDigits <= 26 && twoDigits >= 10) {
                f[i] += f[i - 2];
            }
        }
        return f[s.length()];
    }
}