九章算法题解记录【五】动态规划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真的很严格！
查看3道真题和解析