Posts Tagged ‘2WayDP’
[leetcode] Triangle
Posted on: November 18, 2013
这题其实和robot一样，每个点取决于从上到自己和从左上角到自己哪个小，但是一变成一维dp就做了好久。主要是因为这个不是取决于头顶和左边了，而是头顶和左上角，于是需要一个临时数组。
public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
int res = Integer.MAX_VALUE;
int[] d = new int[triangle.get(triangle.size() - 1).size()];
d[0] = triangle.get(0).get(0);
for (int i = 1; i < triangle.size(); i++) {
int rowSize = triangle.get(i).size();
int[] tmp = new int[rowSize];
for (int j = 0; j < rowSize; j++)
tmp[j] = d[j];
for (int j = 0; j < triangle.get(i).size(); j++) {
int fromAbove = j < rowSize - 1 ? d[j] : Integer.MAX_VALUE;
int fromUpperLeft = j > 0 ? tmp[j - 1] : Integer.MAX_VALUE;
d[j] = Math.min(fromAbove, fromUpperLeft) + triangle.get(i).get(j);
}
}
for (int i = 0; i < d.length; i++) {
res = Math.min(res, d[i]);
}
return res;
}
Tags: 2WayDP
- In: leetcode | summery
- Leave a Comment
- d[i][j]表示从(0, 0)到(i, j)有几种走法，因为只能从上面来或从左边来，所以每次计算只需要d[i – 1][j]和d[i, j – 1]，左上角的全都浪费了。
- f[i]表示从(0,0)到(当前row, j)有几种走法，上面来的就是自己，左边来的已经算好了，所以 f[j] = f[j] + f[j – 1];
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length, n = obstacleGrid[0].length;
// one way DP, f[i] means from (0, 0) to (currRow, i) has how many ways
int f[] = new int[n];
f[0] = obstacleGrid[0][0] > 0 ? 0 : 1;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) { //comes from above or left
if (obstacleGrid[i][j] > 0) {
f[j] = 0;
} else {
if (j == 0) //first col only from above
f[j] = f[j];
else
f[j] = f[j] + f[j - 1];
}
}
}
return f[n - 1];
}
[leetcode] Palindrome Partitioning 2 | 一个String最少切几刀能让分成的substring全是palindrome
Posted on: October 20, 2013
非常非常难，用dfs完全过不了。即使把每个substring是不是palindrome全算好了放在cache里也会挂。必须dp了。
算法：
- 首先把每个substring是不是palindrome先二维dp的做出来，参见上一题的分析。其实这一步可以合在下一步里，但是下一步本身的logic就够难想了，所以这里分开来写。
- 一维dp（为神马是一维啊！！头一次看这样的一维啊！！一维dp却是两层循环啊卧槽！！！），d[i]表示str[i..n]最少切几刀能保证substring全是palindrome。
- 把d[i]先赋成最大值。
- i从后往前，然后j在每个i处从前往后。这样做就能保证在i处，i + 1…j – 1的所有两两combination（中间的小节substring）都已经算出来了，就能用了。如果str[i, j]是个palindrome，那么可以在j 和j + 1中间切一刀，这样的#就是d[j + 1] + 1（[i..j], 一刀, [j + 1..本来有几刀]）。这样切法可能就比之前算的d[i]小了，于是update。
public int minCut(String s) {
int n = s.length();
boolean[][] isPalin = new boolean[n][n];
for (int i = n - 1; i >= 0; i--) { // i is always <= j
for (int j = i; j < n; j++) {
boolean isPalindrome = s.charAt(i) == s.charAt(j)
&& (j - i < 2 || isPalin[i + 1][j - 1]);
isPalin[i][j] = isPalindrome;
}
}
int[] d = new int[n];
// initialize as cut between every letter
for (int i = 0; i < n; i++) {
d[i] = n - 1 - i;
}
for (int i = n - 1; i >= 0; i--) {
for (int j = i; j < n; j++) {
if (isPalin[i][j]) {
if (j == n - 1)
d[i] = 0;
else
d[i] = Math.min(d[i], d[j + 1] + 1);
}
}
}
return d[0];
}
- In: classic | summery
- Leave a Comment
比如abcdefg, defmnabs，最长公共subtring是def。
又是二维DP求String的最优解。居然还是算法课作业做过，真是一点印象也木有了。
- d[i][j] : A[0…i]和B[0…j]的最长公共后缀的长度
- d[i][j] =
- A[i] == B[j] : d[i][j] = d[i – 1][j – 1] + 1 //公共后缀多了当前这个char
- A[i] != B[j] : d[i][j] = 0//断开了，无公共后缀了
总结一下二维DP解String题的做法：
- 一个String, d[i][j]表示A[i…j]的某个最优解
- 两个String, d[i][j]表示A[0…i], B[0…j]的某个比较方式的最优解
- In: leetcode
- 3 Comments
这是好难好难的二维DP题。尽管知道两个String比较很可能是二维DP，但是状态方程真是不好定义；定义了关系也特别不直观。
A: RABBBIT; B: RABBIT
- d[i][j]: A[0…i]里面出现了几次B[0…j]，比如RAB里出现了几次RA
- d[i][j] =
- if A[i] != B[j]，比如RABC和RAB，那么C(A[i]就得被删除，d[i][j]就是RAB在RAB包含的之前算过的情况d[i – 1][j]
- if A[i] == B[j]，比如RABB和RAB，那么
- 可以把RABB的第二个B删除得到RAB，所以d[i][j]最少也是d[i – 1][j]
- 可以用RABB的第二个B直接对应RAB的那个B消掉，所以相当于A=RAB和B=RA，d[i][j] += d[i – 1][j – 1]
- 初始值就是二维DP那么做就行了。
- 这个是真心难想通。还得多做多练习。
public int numDistinct(String S, String T) {
if (T.length() > S.length())
return 0;
char[] A = S.toCharArray();
char[] B = T.toCharArray();
int[][] d = new int [A.length][B.length];
d[0][0] = A[0] == B[0] ? 1 : 0;
int count = d[0][0];
for (int i = 1; i < A.length; i++) {
if (A[i] == B[0])
count++;
d[i][0] = count;
}
for (int j = 1; j < B.length; j++) {
d[0][j] = 0;
}
for (int i = 1; i < A.length; i++) {
for (int j = 1; j < B.length; j++) {
if (A[i] == B[j]) {
d[i][j] = d[i - 1][j] + d[i - 1][j - 1];
} else {
d[i][j] = d[i - 1][j];
}
}
}
return d[A.length - 1][B.length - 1];
}
题目：给一个string，找这个str里面最长的中心对称substring
这个题上来就想一维dp，然后挣扎半天做不出来（找不到一维的d[i]和d[i + 1]的直接关系）。然后上网查答案，原来用二维dp做，而且速度是O(n^2)。其实这题上来就应该先想暴力，然后知道暴力的速度是n^3，然后想办法降一维，别上来就强迫自己O(n)！
二维dp:
- d[i][j]是个boolean，表示(i, j)这个substring是不是中心对称。
- d[i][j]
- 正常情况下，d[i][j] = true when 1.A[i]==A[j] 2. d[i + 1][j – 1] == true (中间那部分已经中心对称了)
- 处理i+1, j-1出界和左边反而大于右边的情况：
- 当i == j时，d[i][j] = 1（一个字母肯定是中心对称）
- 当i == j – 1时，说明两个字符是连着的，看A[i]是否==A[j]就行
- 这个题的坑爹之处在于正常i从0~last, j从0~last那么循环不行。因为d[i][j]用到了d[i + 1][j – 1]，说明i要从后往前，j则要从前往后。导致二层循环是这种顺序：
for (int i = last; i >= 0; i–)
for(int j = i; j <= last; j++)
因为这事想了半天，有点焦躁。
不用二维数组的算法（直接按中心对称的定义来，而不是每个pair算一遍，可以省一维空间）：
- 以每个元素以及间隔为中心（共2 * n – 1个），以相同的速度往两侧扩张，直到两边儿的值不相等了，说明palindrome在此打破，于是输出。这样每次输出的肯定是以当前这个点为中心最长的palindrome）
- 这样过一遍数组，最长的就出来了。
public String longestPalindrome(String s) {
String res = "";
for (int i = 0; i < s.length(); i++) {
String odd = expand(s, i, i);
String even = expand(s, i, i + 1);
String longer = odd.length() > even.length() ? odd : even;
res = longer.length() > res.length() ? longer : res;
}
return res;
}
private String expand(String s, int i, int j) {
while (i >= 0 && j < s.length() && s.charAt(i) == s.charAt(j)) {
i--;
j++;
}
return s.substring(i + 1, j);
}
卧槽这道还真自己做出来了。感觉是二维DP，尽管没让求什么最大最小个数之类的，只是boolean，但是递推关系还是有的。其实只要把状态敢于定义出来（旁边标注物理意义），状态转移方程就能写出来了。然后就是处理最开始。思路：
- 一开始是这么定义的：d[i][j]: whether s1[0, i]的substring和s2[0, j]的substring能够cross match s3[0, i + j + 1]这个substring。比如ab和c，即(0, 1), (0, 0)，能否合起来是acb(0, 2)。要点是s3的index要+1，这个一开始就想错了直接i + j的。
- d[i][j] = s3[i + j + 1] == s2[j] && d[i][j – 1] == true （用第s2的j个来填s3的i + j + 1个能成功）， OR s3[i + j + 1] == s1[i] && d[i – 1][j] == true （用第s1的i个来填s3的i + j + 1个能成功）
- d[i][j]物理意义一定要搞清楚，因为d[0][0]说明拿了两个元素，那么它对应的是长度为2的s3，这index干脆就乱套了。这个时候，换一种方式定义：d[0][0]表示从s1中拿0个，s2中拿0个，然后组成s3（长度为0 + 0)能不能成。这个肯定是true。d[1][0]就能表达只从s1中拿一个，s2中不拿，然后组成长度为1的s3这种make sense的意义了。这样i, j就要一直到=size这么大。所以之前的i + j + 1改成i + j – 1，才能真的往string里charAt。
public boolean isInterleave(String s1, String s2, String s3) {
if (s3.length() != s1.length() + s2.length())
return false;
boolean[][] d = new boolean[s1.length() + 1][s2.length() + 1];
d[0][0] = true;
for (int i = 0; i <= s1.length(); i++) {
for (int j = 0; j <= s2.length(); j++) {
if (j > 0 && s3.charAt(i + j - 1) == s2.charAt(j - 1) && d[i][j - 1])
d[i][j] = true;
else if (i > 0 && s3.charAt(i + j - 1) == s1.charAt(i - 1) && d[i - 1][j])
d[i][j] = true;
}
}
return d[s1.length()][s2.length()];
}
[leetcode] Edit Distance | 一个string转成另一个string最少要几次operation(增加、删除或者替换一个字符）
Posted on: July 16, 2013
将一个字符串变成另外一个字符串所用的最少操作数，每次只能增加、删除或者替换一个字符。如lamb -> slave
这是经典二维DP题。希望做完这个能掌握二维dp要领，因为实在是不够直观。
思路
- 状态：d[i][j]表示将A的0~i这个substring转化成b的0~j这个substring要的最少次数。
- 所以在二维递归的时候，我们一直有三个已经算好的值：（假设 i = m, j = v，即想算lam->slav)
- d[i-1][j-1]: A, B不算当前char，把A转成B最少要几步 (la -> sla)
- d[i-1][j]: A不算当前char，转成B最少要几步 (la -> slav)
- d[i][j – 1]: A转成B比当前char少一个，最少要几步 (lam -> sla)
- 这样的话，怎么由介三个推d[i][j]呢？
- (la -> sla)已经算好了，所以看m和v是不是同一个字符，是的话，直接d[i][j]就=d[i-1][j-1]；不是的话，相当于替换第m成v，lam就能变成slav了，即步数+1。
- (la -> slav)已经算好，所以现在处理lam怎么办呢？删一个m成la就行了，因为已经知道怎么把la变成slav了。即步数+1。
- (lam -> sla)已经算好，所以后面加一个v就行了，lamv就能变成slav了，即步数+1。
- 二维dp一定要先写出来已经有什么了，并且有的这三个东西的物理意义。这种求最小的，肯定是dp的，就别花时间自我怀疑了。
int minDistance(String word1, String word2) {
int[][] d = new int[word1.length()][word2.length()];
boolean hadSameInA = false;
boolean hadSameInB = false;
if (word1.charAt(0) == word2.charAt(0)) {
d[0][0] = 0;
hadSameInA = true;
hadSameInB = true;
} else {
d[0][0] = 1;
}
//do the same for string B. 但是别人做的都是直接assign i,不考虑有相同的情况。那是怎么回事？
for (int i = 1; i < word1.length(); i++) {
for (int j = 1; j < word2.length(); j++) {
if (word1.charAt(i) == word2.charAt(j))
d[i][j] = d[i - 1][j - 1];
else {
d[i][j] = Math.min(d[i - 1][j - 1] + 1, Math.min(d[i][j - 1] + 1, d[i - 1][j] + 1));
}
return d[word1.length - 1][word2.length - 1];
Lexi's Leetcode solutions 