Lexi's Leetcode solutions

Posts Tagged ‘2WayDP

这题其实和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;
}
Advertisements
Tags:
  • 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];
}
Tags: ,

非常非常难,用dfs完全过不了。即使把每个substring是不是palindrome全算好了放在cache里也会挂。必须dp了。

算法:

  1. 首先把每个substring是不是palindrome先二维dp的做出来,参见上一题的分析。其实这一步可以合在下一步里,但是下一步本身的logic就够难想了,所以这里分开来写。
  2. 一维dp(为神马是一维啊!!头一次看这样的一维啊!!一维dp却是两层循环啊卧槽!!!),d[i]表示str[i..n]最少切几刀能保证substring全是palindrome。
  3. 把d[i]先赋成最大值。
  4. 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];
}

比如abcdefg, defmnabs,最长公共subtring是def。

又是二维DP求String的最优解。居然还是算法课作业做过,真是一点印象也木有了。

  • d[i][j] : A[0…i]和B[0…j]的最长公共后缀的长度
  • d[i][j] =
    1. A[i] == B[j] : d[i][j] = d[i – 1][j – 1] + 1 //公共后缀多了当前这个char
    2. 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]的某个比较方式的最优解

这是好难好难的二维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,那么
      1. 可以把RABB的第二个B删除得到RAB,所以d[i][j]最少也是d[i – 1][j]
      2. 可以用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:

  1. d[i][j]是个boolean,表示(i, j)这个substring是不是中心对称。
  2. 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]就行
  3. 这个题的坑爹之处在于正常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算一遍,可以省一维空间):

  1. 以每个元素以及间隔为中心(共2 * n – 1个),以相同的速度往两侧扩张,直到两边儿的值不相等了,说明palindrome在此打破,于是输出。这样每次输出的肯定是以当前这个点为中心最长的palindrome)
  2. 这样过一遍数组,最长的就出来了。
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,但是递推关系还是有的。其实只要把状态敢于定义出来(旁边标注物理意义),状态转移方程就能写出来了。然后就是处理最开始。思路:

  1. 一开始是这么定义的: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的。
  2. 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个能成功)
  3. 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()];
}
Tags: ,