继续上一篇的的单序列
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<String> 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<String> 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<String> 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<String> 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<String> 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真的很严格！
三 Two Sequences Dp state: f[i][j]代表了第一个sequence的前i个数字 /字符 配上第二个sequence的前j个… function: f[i][j] = 研究第i个和第j个的匹配关系 intialize: f[i][0] 和 f[0][i] answer: f[s1.length()][s2.length()]
3 Longest Common Subsequence http://www.lintcode.com/problem/longest-common-subsequence/
public class Solution { /** * @param A: A string * @param B: A string * @return: The length of longest common subsequence of A and B */ public int longestCommonSubsequence(String A, String B) { // 错误输入条件 if (A == null || B == null) return 0; // 状态定义 dp[i][j] 从i到j的LCS int[][] dp = new int[A.length() + 1][B.length() + 1]; // 初始化 // 递归求解 for (int i = 0; i < A.length(); i++) { for (int j = 0; j < B.length(); j++) { if (A.charAt(i) == B.charAt(j)){ dp[i + 1][j + 1] = Math.max(dp[i][j + 1], dp[i + 1][j]); dp[i + 1][j + 1] = Math.max(dp[i][j] + 1, dp[i + 1][j + 1]); } else { dp[i + 1][j + 1] = Math.max(dp[i + 1][j], dp[i][j + 1]); } } } // 答案 return dp[A.length()][B.length()]; } }本题开始没AC原因是状态转移方程没写出来，应该是：
f[i][j] = MAX(f[i-1][j], f[i][j-1], f[i-1][j-1] + 1) // a[i] == b[j] = MAX(f[i-1][j], f[i][j-1]) // a[i] != b[j]改了之后一遍AC，还是得画个矩阵并结合一些case来确定转移条件，双序列最重要的是三个方向：左上！左！右！ 与2Dmatrix区别在于双序列并无主次之分，所以有三个方向。
得出一个小trick，序列型问题一般都要比长度大1
4 Longest Common SubString http://www.lintcode.com/problem/longest-common-substring/
public int longestCommonSubstring(String A, String B) { if (A == null || A.length() == 0 || B == null || B.length() == 0){ return 0; } // 状态定义 dp[i][j] 表示从i到j的LCSubString int[][] dp = new int[A.length() + 1][B.length() + 1]; // 初始化 第一行第一列为0 // 递归求解 for (int i = 0; i < A.length(); i++) { for (int j = 0; j < B.length(); j++) { if (A.charAt(i) == B.charAt(j)){ dp[i + 1][j + 1] = dp[i][j] + 1; } else { dp[i + 1][j + 1] = 0; } } } // 答案 MAX(f[0..a.length()][0..b.length()]) int max = Integer.MIN_VALUE; for (int i = 0; i <= A.length(); i++) { for (int j = 0; j <= B.length(); j++) max = Math.max(max, dp[i][j]); } return max; }转移条件是：
function: f[i][j] = f[i-1][j-1] + 1 // a[i] == b[j] = 0 // a[i] != b[j]同时，答案是 dp矩阵中所有元素的最大值。
解题思路： 一刷未AC，把答案想的太简单，总是想要在终止位置得到结果，但实际上结果可以保存在整个dp矩阵中，并不会提升时空复杂度！ SubString问题的启发：在dp矩阵全部值中得到最大值！
5 Edit Distance http://www.lintcode.com/problem/edit-distance/
public class EditDistance { public int minDistance(String word1, String word2) { int size1 = word1.length(); int size2 = word2.length(); //子串都应包含空串，所以长度都+1 int[][] dp = new int[size1 + 1][size2 + 1]; for (int i = 0; i <= size1; i++) { dp[i][0] = i; } for (int j = 0; j <= size2; j++) { dp[0][j] = j; } //都从不为空串的第一个子串开始 for (int i = 1; i <= size1; i++) { for (int j = 1; j <=size2; j++) { if (word1.charAt(i-1) == word2.charAt(j-1)) { dp[i][j] = dp[i-1][j-1]; } else { dp[i][j] = Math.min(Math.min(dp[i-1][j-1], dp[i][j-1]), dp[i-1][j]) + 1; } } } return dp[size1][size2]; } }四步走，转移方程三个方向！
state: f[i][j]a的前i个字符最少要用几次编辑可 以变成b的前j个字符 function: f[i][j] = MIN(f[i-1][j]+1, f[i][j-1]+1, f[i-1][j-1]) // a[i] == b[j] = MIN(f[i-1][j]+1, f[i][j-1]+1, f[i-1][j-1]+1) // a[i] != b[j] intialize: f[i][0] = i, f[0][j] = j answer: f[a.length()][b.length()]6 Distinct Subsequences http://www.lintcode.com/problem/distinct-subsequences/
class Solution { /** * @param S: A string * @param T: A string * @return: Count the number of distinct subsequences */ public int numDistinct(String S, String T) { // 错误输入条件 if (S == null || T == null){ return 0; } // 状态定义 dp[i][j]为长度为i的子串T在长度为j的母串S中出现次数 int[][] dp = new int[T.length() + 1][S.length() + 1]; // 初始化 for (int i = 0; i <= S.length(); i++) { dp[0][i] = 1; } // 递归求解 for (int i = 1; i <= T.length(); i++) { for (int j = 1; j <= S.length(); j++) { if (T.charAt(i - 1) == S.charAt(j - 1)){ dp[i][j] = dp[i][j - 1] + dp[i - 1][j - 1]; } else { dp[i][j] = dp[i][j - 1]; } } } // 答案 return dp[T.length()][S.length()]; } }本题首先状态定义，应该i是子串j是母串，每次增加母串，相等时则分为用此结尾和不用此结尾 不等时则说明加不加这个结尾都一样。 注意初始化时 子串为空 则母串0 - slength 都为1. 理解了很久，说明双序列需要确定长度，有主次。
可以优化空间复杂度，只用一维矩阵,但是目前i与i i-1都有关，因此改写成i是母串 j是子串形式，依然AC
class Solution { /** * @param S: A string * @param T: A string * @return: Count the number of distinct subsequences */ public int numDistinct(String S, String T) { // 错误输入条件 if (S == null || T == null){ return 0; } // 状态定义 dp[i][j]为长度为i的子串T在长度为j的母串S中出现次数 int[][] dp = new int[S.length() + 1][T.length() + 1]; // 初始化 for (int i = 0; i <= S.length(); i++) { dp[i][0] = 1; } // 递归求解 for (int i = 1; i <= S.length(); i++) { for (int j = 1; j <= T.length(); j++) { if (S.charAt(i - 1) == T.charAt(j - 1)){ dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1]; } else { dp[i][j] = dp[i - 1][j]; } } } // 答案 return dp[S.length()][T.length()]; } }此时，ｉ只与ｉ－１有关，进行矩阵压缩。
class Solution { /** * @param S: A string * @param T: A string * @return: Count the number of distinct subsequences */ public int numDistinct(String S, String T) { // 错误输入条件 if (S == null || T == null){ return 0; } // 状态定义 dp[i][j]为长度为i的子串T在长度为j的母串S中出现次数 int[] dp = new int[T.length() + 1]; // 初始化 dp[0] = 1; // 递归求解 for (int i = 1; i <= S.length(); i++) { for (int j = T.length(); j >= 1; j--) { if (S.charAt(i - 1) == T.charAt(j - 1)){ dp[j] = dp[j] + dp[j - 1]; } else { dp[j] = dp[j]; } } } // 答案 return dp[T.length()]; } }轻松改成一维ｄｐ 注意此时ｊ循环是逆序的，背包思想无脑改。
7 Interleaving String http://www.lintcode.com/problem/interleaving-string/ 开始的错误代码
public class InterleavingString { /** * @param s1: A string * @param s2: A string * @param s3: A string * @return: Determine whether s3 is formed by interleaving of s1 and s2 */ public boolean isInterleave(String s1, String s2, String s3) { // 错误输入条件，排除了所有为null的情况 if (s3 == null || s3.length() == 0){ if ((s1 == null || s1.length() == 0) && (s2 == null || s2.length() == 0)){ return true; } else { return false; } } else { if (s1 == null || s1.length() == 0){ if (s2.equals(s3)){ return true; } else { return false; } } else if (s2 == null || s2.length() == 0){ if (s1.equals(s3)){ return true; } else { return false; } } } if ((s1.length() + s2.length()) != s3.length()){ return false; } // 状态定义 dp[i][j]表示 str1的0 - i 与 str2的 0 - j 可以构成长度为i + j的交叉字符串 boolean[][] dp = new boolean[s1.length() + 1][s2.length() + 1]; // 初始化 dp[0][0] = true; // 递归求解 for (int i = 0; i < s1.length(); i++) { for (int j = 0; j < s2.length(); j++) { if (dp[i][j]){ if (s1.charAt(i) == s3.charAt(i + j)){ dp[i + 1][j] = true; } if (s2.charAt(j) == s3.charAt(i + j)){ dp[i][j + 1] = true; } } } } // 答案 for (int i = 0; i <= s1.length() ; i++) { for (int j = 0; j <= s2.length(); j++) { System.out.print(dp[i][j] + " "); } System.out.println(""); } return (dp[s1.length()][s2.length() - 1] && s2.charAt(s2.length() - 1) == s3.charAt(s1.length() + s2.length() - 1)) || (dp[s1.length() - 1][s2.length()] && s1.charAt(s1.length() - 1) == s3.charAt(s1.length() + s2.length() - 1)); } }解题思路： 本题的dp方程定义是对的，但是有几点错误：
初始化条件时，只初始化了原点，应该尽力匹配，完全初始化第一列的结果转换方程想错了思路，用该点的位置来推后面的点。。。违背了DP的基本思路。。修改的状态转化方程如下：
dp[i][j] = dp[i - 1][j] | dp[i][j - 1] s1.charAt(i - 1) == s3.charAt(i + j - 1) == s2.charAt(j - 1) （第一次做木有考虑到这种情况） dp[i][j] = dp[i - 1][j] s1.charAt(i - 1) == s3.charAt(i + j - 1); dp[i][j] = dp[i][j - 1] s2.charAt(j - 1) == s3.charAt(i + j - 1);改正后的代码如下：
public class Solution { /** * @param s1: A string * @param s2: A string * @param s3: A string * @return: Determine whether s3 is formed by interleaving of s1 and s2 */ public boolean isInterleave(String s1, String s2, String s3) { // 错误输入条件，排除了所有为null的情况 if (s3 == null || s3.length() == 0){ if ((s1 == null || s1.length() == 0) && (s2 == null || s2.length() == 0)){ return true; } else { return false; } } else { if (s1 == null || s1.length() == 0){ if (s2.equals(s3)){ return true; } else { return false; } } else if (s2 == null || s2.length() == 0){ if (s1.equals(s3)){ return true; } else { return false; } } } if ((s1.length() + s2.length()) != s3.length()){ return false; } // 状态定义 dp[i][j]表示 str1的0 - i 与 str2的 0 - j 可以构成长度为i + j的交叉字符串 boolean[][] dp = new boolean[s1.length() + 1][s2.length() + 1]; // 初始化 dp[0][0] = true; for (int i = 0; i < s1.length(); i++) { if (s1.charAt(i) == s3.charAt(i)){ dp[i + 1][0] = true; } else { break; } } for (int i = 0; i < s2.length(); i++) { if (s2.charAt(i) == s3.charAt(i)){ dp[0][i + 1] = true; } else { break; } } // 递归求解 for (int i = 1; i <= s1.length(); i++) { for (int j = 1; j <= s2.length(); j++) { if (s1.charAt(i - 1) == s3.charAt(i + j - 1)){ dp[i][j] |= dp[i - 1][j]; } if (s2.charAt(j - 1) == s3.charAt(i + j - 1)){ dp[i][j] |= dp[i][j - 1]; } } } return dp[s1.length()][s2.length()]; } }注意用的是 |= 只要上边右边有一个满足即可。 双序列在使用了dp[+1][+1]之后，还是尽量从1开始到<= charAt(i - 1) dp[i][j] = dp[i - 1][j - 1]此类。 从此统一！不然在charAt(i + j的时候可能会出现不知名bug)…
四 其他类别问题之背包类 8 Backpack https://www.lintcode.cn/problem/backpack/discuss （从此变成cn域名，一秒进入）
public class BackPack { /** * @param m: An integer m denotes the size of a backpack * @param A: Given n items with size A[i] * @return: The maximum size */ public int backPack(int m, int[] A) { if (m == 0 || A == null || A.length == 0){ return 0; } // 状态定义 dp[i + 1][j]为前 i 个物品中选出重量不超过j时总价值的最大值 int[][] dp = new int[A.length + 1][m + 1]; // 初始化 均为0 // 递归求解 for (int i = 0; i < A.length; i++) { for (int j = 1; j <= m ; j++) { if (A[i] > j){ dp[i + 1][j] = dp[i][j]; } else { dp[i + 1][j] = Math.max(dp[i][j], dp[i][j - A[i]] + A[i]); } } } // 答案 return dp[A.length][m]; } }01背包问题， 价值等于重量。其实贪心也能做。一遍DP方法AC，关键点在于一个物品不断放大他的重量，其实可以优化成一维空间的。。。
9 Backpack II https://www.lintcode.cn/problem/backpack-ii/description
public class Solution { /** * @param m: An integer m denotes the size of a backpack * @param A: Given n items with size A[i] * @param V: Given n items with value V[i] * @return: The maximum value */ public int backPackII(int m, int[] A, int[] V) { if (m == 0 || A == null || A.length == 0){ return 0; } // 状态定义 dp[i + 1][j]为前 i 个物品中选出重量不超过j时总价值的最大值 int[][] dp = new int[A.length + 1][m + 1]; // 初始化 均为0 // 递归求解 for (int i = 0; i < A.length; i++) { for (int j = 1; j <= m ; j++) { if (A[i] > j){ dp[i + 1][j] = dp[i][j]; } else { dp[i + 1][j] = Math.max(dp[i][j], dp[i][j - A[i]] + V[i]); } } } // 答案 return dp[A.length][m]; } }01背包。 稍微改了一点转移方程。一遍AC
10 最小调整代价 https://www.lintcode.cn/problem/minimum-adjustment-cost/description 这道题比较难想。。dp[i][j]表示第i的数变成j的最小调整代价。 对于第i个数，其取值为j的话，那么i-1的时候，其取值范围为[j-target][j+target]。则转移方程可知为：
for k = j-target to j+target: dp[i][j]=min(dp[i][j], dp[i-1][k]+abs(j-A[i]))代码如下：也是很多校招题的母题，考虑每个数的所有可能性，最后遍历求出最小代价
public class Solution { /* * @param A: An integer array * @param target: An integer * @return: An integer */ public int MinAdjustmentCost(List<Integer> A, int target) { if (A == null || A.size() == 0) return 0; int max = getMax(new ArrayList<Integer>(A)); // 状态定义 dp[i][j] 表示走到第i个数，并且把其变成j的最小步数 （j = 0 ~ 100） int[][] dp = new int[A.size()][max + 1]; // 初始化 for (int i = 0; i <= max ; i++) { dp[0][i] = Math.abs(i - A.get(0)); } // 递归求解 dp for (int i = 1; i < A.size() ; i++) { for (int j = 1; j <= max; j++) { dp[i][j] = Integer.MAX_VALUE; for(int k = Math.max(1, j - target); k <= Math.min(max, j + target); k++){ dp[i][j] = Math.min(dp[i][j], dp[i - 1][k] + Math.abs(j - A.get(i))); } } } // 答案 int min = Integer.MAX_VALUE; for (int i = 1; i <= max; i++) { min = Math.min(min, dp[A.size() - 1][i]); } return min; } private int getMax(ArrayList<Integer> A) { int max = A.get(0); for (int i = 1; i < A.size(); i++) { max = Math.max(max, A.get(i)); } return max; } }debug了很久。。。 1.初始化条件时，就要把dp[0][i]给赋值成 k - A[i]； 2. k的上界下界要加条件限制 3. 要把所有的代价要包含一个绝对值。 4. target == 0时不能直接返回0.。
最后的答案是 j取遍 0 - max的最小代价。
11 ksum https://www.lintcode.cn/problem/k-sum/description 经典题，三维dp并优化成二维 先写三维：
public class Solution { public int kSum(int[] A, int k, int target) { if (A == null || A.length == 0 || k <= 0 || target <= 0) { return 0; } int sum = 0; for (int i = 0; i < A.length; i++) { sum += A[i]; } if (sum < target) { return 0; } if (sum == target) { return 1; } // 方程定义 dp[i][j][k]表示 前0 - i个数中选j个 和为k的方案数总和 int[][][] dp = new int[A.length + 1][k + 1][target + 1]; // 初始化 选k个和为0有一种 for (int i = 0; i <= A.length; i++) { dp[i][0][0] = 1; } // 递推 for (int i = 1; i <= A.length; i++) { for (int j = 1; j <= k && j <= i; j++) { for (int t = 0; t <= target; t++) { if (A[i - 1] <= t) { dp[i][j][t] = dp[i - 1][j - 1][t - A[i - 1]] + dp[i - 1][j][t]; //放的进去，分为两种情况 放不放，方案数量相加 } else { dp[i][j][t] = dp[i - 1][j][t]; // 给一个初始值，放不进去就等于它的兄弟 } } } } return dp[A.length][k][target]; } }开始没做出来是没想好状态转换方程，同时写了A[i - 1] < t 导致没有加，后来多加了一个等号就行。。
不能优化成2D空间，因为每次递推与i-1有关，j t并没有形成只与上一个有关的性质。
五 其他类别问题之区间类
博弈DP 1 硬币排成线 https://www.lintcode.cn/problem/coins-in-a-line/note/177781
public class Solution { /** * @param n: An integer * @return: A boolean which equals to true if the first player will win */ public boolean firstWillWin(int n) { if (n <= 0) { return false; } if (n == 1 || n == 2) { return true; } boolean[] dp = new boolean[n + 1]; dp[1] = true; dp[2] = true; for (int i = 3; i <= n; i++) { dp[i] = !dp[i - 1] || !dp[i - 2]; } return dp[n]; } }解题思路 上两步先手假如能赢，则这步先手必败 也可直接 return !(n % 3 == 0)
2 硬币排成线II https://www.lintcode.cn/problem/coins-in-a-line-ii/description
public class Solution { public boolean firstWillWin(int[] values) { int n = values.length; if(values==null || n==0){ return false; } if(n <= 2){ return true; } int[] DP = new int[n+1]; DP[n]=0; DP[n-1]=values[n-1]; DP[n-2]=values[n-1]+values[n-2]; DP[n-3]=values[n-2]+values[n-3]; for(int i=n-4;i>=0;i--){ //我们取一个数或取两个数 DP[i]=values[i]+Math.min(DP[i+2],DP[i+3]); DP[i]=Math.max(DP[i],values[i]+values[i+1]+Math.min(DP[i+3],DP[i+4])); } int sum=0; for(int i:values){ sum+=i; } return DP[0]*2>sum; } }解题思路： 定义dp[i]表示从i到end能取到的最大值 当我们在i处，有两种选择： 1.若取values[i]，对方可以取values[i+1] 或者values[i+1] + values[i+2] 当对方取values[i+1] 后 ，我们只能从 i+2 到end内取，我们所取得最大值是dp[i+2], 注意：对方所选取的结果一定是使得我们以后选取的值最小 当对方取values[i+1] + values[i+2]后，我们只能从i+3到end内取，我们所取得最大值是dp[i+3]。 此时：dp[i] = values[i] + min(dp[i+2],dp[i+3]) , 注意：对方所选取的结果一定是使得我们以后选取的值最小 2.若取values[i] + values[i+1],对方可取values[i+2] 或者values[i+2] + values[i+3] 当对方取values[i+2]后，我们只能从i+3到end内取，我们取得最大值是dp[i+3] 当对方取values[i+2]+values[i+3]后，我们只能从i+4到end内去，我们取得最大值是dp[i+4] 此时：dp[i] = values[i] + values[i+1]+min(dp[i+3],dp[i+4]) 这里的取最小值和上面一样的意思，对方选取过之后的值一定是使得我们选取的值最小，对方不傻并且还很聪明 最后我们可以取上面两个dp[i]的最大值，就是答案，这里意思是：对方留得差的方案中，我们选取的最大值。
3 硬币排成线III https://www.lintcode.cn/problem/coins-in-a-line-iii/description
class Solution { /** * @param values: a vector of integers * @return: a boolean which equals to true if the first player will win */ public boolean firstWillWin(int[] values) { int n = values.length; if (n <= 2) return true; int[][] dp = new int[n][n]; for (int i = 0; i < n; i++) dp[i][i] = values[i]; for (int i = n-2; i >= 0; i--) for (int j = i+1; j < n; j++) dp[i][j] = Math.max(values[i] - dp[i+1][j], values[j] - dp[i][j-1]); return dp[0][n-1] > 0; } };解题思路： 定义dp[i][j]表示从i到j这个区间，先手能比后手多拿的分数 对于某一时刻的状态i，j，只有两个拿硬币的方法，一个是从左，一个是从右，选取其中的最大值，也就是 dp[i][j] = max(values[i] - dp[i+1][j], values[j] - dp[i][j-1]) 对于初始状态，dp[i][i] = values[i]，因为只有一个硬币。 trick：n为偶数时，先手是必胜的。
4 Scramble String https://www.lintcode.cn/problem/scramble-string/description
public class Solution { /** * @param s1: A string * @param s2: Another string * @return: whether s2 is a scrambled string of s1 */ public boolean isScramble(String s1, String s2) { if (s1.length() != s2.length()) { return false; } int len = s1.length(); boolean[][][] dp = new boolean[len][len][len]; // dp[i][j][k-1] == true: s1[i:i+k] is scramble of s2[j:j+k] for (int k = 0; k < len; k++) { for (int i = 0; i + k < len; i++) { for (int j = 0; j + k < len; j++) { if (k == 0) { dp[i][j][k] = s1.charAt(i) == s2.charAt(j); } else { for (int l = 0; l < k && !dp[i][j][k]; l++) { dp[i][j][k] = dp[i][j][l] && dp[i + l + 1][j + l + 1][k - l - 1] || dp[i][j + k - l][l] && dp[i + l + 1][j][k - l - 1]; } } } } } return dp[0][0][len - 1]; } }解题思路： 太困了，随便找的别人的答案，区间型DP，有空再看。 动态规划。三维动态规划数组dp[i][j][k]表示存在s1[i:i+k]的二叉树表示t1和s2[j:j+k]的二叉树表示t2，使得t1和t2只相差一次左右子树置换 计算dp[i][j][k]时，l从1遍历到k-1，用l对s1[i:i+k]和s2[j:j+k]进行分割，判断分割后的字符串是否相等或互为置换 注：实际代码中为了减少dp数组大小，将上述所有k映射为k-1，所有l映射为l-1
或者
这是一道三维动态规划的题目，我们提出维护量res[i][j][n]，其中i是s1的起始字符编号，j是s2的起始字符编号， 而n是当前的字符串长度；res[i][j][len]表示的是：以i和j分别为s1和s2起点的长度为len的字符串是不是互为scramble。 有了维护量我们接下来看看递推式，也就是怎么根据历史信息来得到res[i][j][len]。 判断这个是不是满足，其实我们首先是把当前s1[i，……，i+len-1]字符串劈一刀分成两部分，然后分两种情况： 第一种情况是：左边和s2[j，……，j+len-1]左边部分是不是scramble，以及右边和s2[j…j+len-1]右边部分是不是scramble； 第二种情况是：左边和s2[j…j+len-1]右边部分是不是scramble，以及右边和s2[j…j+len-1]左边部分是不是scramble。 以上两种情况只要有一种成立，就说明s1[i，……，i+len-1]和s2[j，……，j+len-1]是scramble的。 对于判断这些左右部分是不是scramble，我们是有历史信息的， 因为长度小于n的所有情况我们都在前面求解过了（也就是长度是最外层循环）。 上面说的是劈一刀的情况，对于s1[i，……，i+len-1]我们有len-1种劈法， 在这些劈法中只要有一种成立，那么两个串就是scramble的。 总结起来递推式如下： res[i][j][len] ||=（（res[i][j][k]&&res[i+k][j+k][len-k]）||（res[i][j+len-k][k]&&res[i+k][j][len-k]）） 对于所有1<=k<len，也就是对于所有len-1种劈法的结果求 或运算。 因为信息都是计算过的，对于每种劈法只需要常量操作即可完成，因此求解递推式是需要O(len)（因为len-1种劈法）。 总时间复杂度：因为是三维动态规划，需要三层循环，加上每一步需要线行时间求解递推式，所以是O(n^4)。 虽然已经比较高了，但是至少不是指数量级的，动态规划还是有很大优势的，空间复杂度是O(n^3)。
明天复习整理。
