九章算法题解记录【五】动态规划II

继续上一篇的的单序列

1 Palindrome Partitioning II http://www.lintcode.com/problem/palindrome-partitioning-ii/

public class Solution {
    /**
     * @param s: A string
     * @return: An integer
     */
    public int minCut(String s) {
        // 错误输入条件
        if (s == null) {
            return 0;
        }
        // 状态定义 dp[i]表示从0到i位置的最小分割次数
        int[] dp = new int[s.length() + 1];

        // 初始化
        for (int i = 0; i <= s.length() ; i++) {
            dp[i] = i - 1;
        }

        // 递归求解
        for (int i = 2; i <= s.length(); i++) {
            for (int j = i; j >= 1; j--) {
                if (isPalindrome(s.substring(j - 1, i))){
                    dp[i] = Math.min(dp[i], dp[j - 1] + 1);
                }
            }
        }
        // 答案
        return dp[s.length()];
    }

    private boolean isPalindrome(String str){
        if (str == null){
            return true;
        }
        int start = 0, end = str.length() - 1;
        while (start <= end){
            if (str.charAt(start++) != str.charAt(end--)){
                return false;
            }
        }
        return true;
    }
}

debug了很久，原因1 是substring的时候也不能忽略了一个字母的情况，这样就是前面的+1，假如没考虑到就会出错。。。还有一个trick是要new int（length + 1）的数组，并dp = -1 从而全部满足 dp[start] + 1。第三个注意点是假如序列+1 那么第一层循环是 <=
目前这种情况勉强过了leetcode100%，LintCode OOM了只过了96%。。可能要再做优化，但是先看大局。。
优化方案：再加一个二维矩阵保存i到j是否回文。假如没有才计算一遍。（Redis、MySQL缓存思想么？？？似乎一切都是通的。。）

2 Word Break http://www.lintcode.com/problem/word-break/

public class Solution {
    /*
     * @param s: A string
     * @param dict: A dictionary of words dict
     * @return: A boolean
     */
    public boolean wordBreak(String s, Set dict) {
        // 错误输入条件
        if (s == null || dict == null) {
            return false;
        }
        // 状态定义 dp[i]从0到i全部在dict中
        boolean[] dp = new boolean[s.length() + 1];

        // 初始化
        dp[0] = true;

        // 递归求解
        for (int i = 1; i <= s.length(); i++) {
            for (int j = i; j >= 1; j--) {
                if (dict.contains(s.substring(j - 1, i))){
                    dp[i] |= dp[j - 1];
                }
            }
        }
        // 答案
//        for (int i = 0; i < s.length(); i++) {
//            System.out.print(dp[i] + " ");
//        }
        return dp[s.length()];
    }
}

又过了91%。。。本题开始没A的原因是 dp[i]找到一个包含的就break, 应该是其中只要有就行，最后用了|=才能过91%。。

后来优化成：

public class Solution {
    /*
     * @param s: A string
     * @param dict: A dictionary of words dict
     * @return: A boolean
     */
    public boolean wordBreak(String s, Set dict) {
        // 错误输入条件
        if (s == null || dict == null) {
            return false;
        }
        int minLength = getMinLength(dict);

        // 状态定义 dp[i]从0到i全部在dict中
        boolean[] dp = new boolean[s.length() + 1];

        // 初始化
        dp[0] = true;

        // 递归求解
        for (int i = 1; i <= s.length(); i++) {
            for (int j = Math.max(i - minLength + 1, 1); j >= 1; j--) {
                if (dict.contains(s.substring(j - 1, i))){
                    dp[i] |= dp[j - 1];
                }
            }
        }
         //答案
        for (int i = 0; i < s.length(); i++) {
            System.out.print(dp[i] + " ");
        }
        return dp[s.length()];
    }

    private int getMinLength(Set dict) {
        int minLength = Integer.MAX_VALUE;
        for (String s : dict) {
            if (s.length() < minLength) {
                minLength = s.length();
            }
        }
        return minLength;
    }
}

使用了一个MinLength来缩减所需要计算的范围，但是测试用例中dict很小，String很长，这样实际上不能减少多少，依然91%，于是改成了要MaxLength来缩减。

public class Solution {
    /*
     * @param s: A string
     * @param dict: A dictionary of words dict
     * @return: A boolean
     */
    public boolean wordBreak(String s, Set dict) {
        // 错误输入条件
        if (s == null || dict == null) {
            return false;
        }
        int maxLength = getLongestLength(dict);

        // 状态定义 dp[i]从0到i全部在dict中
        boolean[] dp = new boolean[s.length() + 1];

        // 初始化
        dp[0] = true;

        // 递归求解
        for (int i = 1; i <= s.length(); i++) {
            for (int j = Math.max(i - maxLength, 0); j < i; j++) {
                if (dp[j] && dict.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
         //答案
//        for (int i = 0; i < s.length(); i++) {
//            System.out.print(dp[i] + " ");
//        }
        return dp[s.length()];
    }

    private int getLongestLength(Set dict) {
        int maxLength = 0;
        for (String s : dict) {
            if (s.length() > maxLength) {
                maxLength = s.length();
            }
        }
        return maxLength;
    }
}

最后勉强过了UT，还是得结合测试用例做文章。
同时这里把|=的判断改成了dp[i] && contains 则true并break，这样也进行了一些剪枝。
PS. Leetcode中dict是一个List，假如把他变成一个dict则与本题相同，同时beat95%在leetcode上。LintCode真的很严格！