请教一道面试题

机器人从左上方到右下角
规则： 每步只能从 右上， 右边， 右下
基本的dp：dp[i][j] = dp[i - 1][j - 1] + dp[i][j - 1] + dp[i+1][j-1]
Follow up1: optimize space complexity
Follow up2: given 3 points in the matrix, check whether there is a path can go through these 3 points
Follow up3: given 3 points in the matrix, find out all the paths that can go through these 3 points.

请问有哪位大侠可以给一下3个follow up的code吗，学习一下，感激不尽。

follow up1, 我自己写了如下，但是有错误。大侠们能也帮忙看看吗
public static int findPaths2(int m, int n){
    int[] dp = new int[m];
    for(int i = 0; i < m; i++){
      dp[i] = 1;
    }
    for(int i = 1; i < n; i++){
      int[] tmp = new int[m];
      for(int j = 1; j < m; j++){
        tmp[j] = dp[j - 1] + dp[j];
        if(j != m - 1)
           tmp[j] += dp[j + 1];
      }
      dp = tmp;
    }
    return dp[m - 1];
}

drift1981 发表于 2019-9-25 05:49
follow up1, 我自己写了如下，但是有错误。大侠们能也帮忙看看吗
public static int findPaths2(int m, i ...

这个解法在于你没有更新第一个row

public static int findPaths2(int m, int n){
    int[] dp = new int[m];
    for(int i = 0; i < m; i++){
      dp[i][i] = 1;
    }
    for(int i = 1; i < n; i++){
      int[] tmp = new int[m];
      for(int j = 0; j < m; j++){
// 不要遗漏了更新tmp[0]
        if (j != 0)
           tmp[j] += dp[j - 1];

        tmp[j] += dp[j];

        if(j != m - 1)
           tmp[j] += dp[j + 1];
      }
      dp = tmp;
    }
    return dp[m - 1];
}[/i]

psy 发表于 2019-9-25 06:23
这个解法在于你没有更新第一个row

public static int findPaths2(int m, int n){

谢谢回复。

这个和我用如下，最basic的解法的返回答案是不同的，很困惑：

///////
  public static int findPaths1(int m, int n){
    // dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + dp[i + 1][j]
    int[][] dp = new int[m][n];
    for(int i = 0; i < m; i++){
      dp[i][0] = 1;
    }
    for(int j = 0; j < n; j++){
      dp[0][j] = 1;
    }
   
    for(int i = 1; i < m; i++){
      for(int j = 1; j < n; j++){
        dp[i][j] = dp[i - 1][j - 1] + dp[i][j - 1];
        if(i < m - 1){
          dp[i][j] += dp[i + 1][j - 1];
        }
      }
    }
    return dp[m - 1][n - 1];
  }

杨辉三角的基本用法吧。。

dp[i, j] = dp[i - 1, j - 1] + dp[i, j - 1] + dp[i + 1, j - 1]

i为上下， j为左右，越界标0即可。
省空间就是两个数组。

第二问 是否存在就看在不在+1, -1的斜率里面即可。

第三问 拆成3个从左往右的点，分别做一次。

drift1981 发表于 2019-9-25 07:01
谢谢回复。

这个和我用如下，最basic的解法的返回答案是不同的，很困惑：

我assume你的basic解法里dp演变公式没有typo，
dp[i][j] = dp[i - 1][j - 1] + dp[j - 1];
就说解法思想，因为你的基本解法中也没有更新dp[0][i]，你的解法里dp[0][i] 永远都是1，而根据题目描述，这一行是左下，左 的合

1 2 5 。。。
1 3 8 。。。
1 3 8 。。。
1 2 5 。。。

337845818 发表于 2019-9-25 10:35
杨辉三角的基本用法吧。。

dp = dp + dp + dp

请问大侠可以再指导一下吗。
我重新读题，照这种题意。dp[0][0] = 1。从左上角到右下角。 i, j 位置只能从前一列的上中下位置走到。那不是如果row == col, 就只有一条路，如果row > col， 就没有路， 如果row < col, 才有可能有大于一条路？

drift1981 发表于 2019-9-27 07:15
请问大侠可以再指导一下吗。
我重新读题，照这种题意。dp[0][0] = 1。从左上角到右下角。 i, j 位置只能 ...

是的你说的没错， 也就是我写的斜率+1， -1之间才有解。

本质上是个三分树 trinomial tree，不知道你熟悉不熟悉。

感觉用这两个function就应该可以帮助解决所有follow up了吧：

1.     public static boolean reachable(Point src, Point dst) {
   
2.         if (dst.x <= src.x) return false;
   
3.         return Math.abs(dst.y - src.y) <= Math.abs(dst.x - src.x);
   
4.     }
   
5.    
   
6.     public static int numPaths(int height, Point src, Point dst) {
   
7.         if (dst.x <= src.x) return 0;
   
8.         int[] currCol = new int[height];
   
9.         for (int i = 0; i < height; i++) {
   
10.             currCol = 0;
    
11.         }
    
12.         currCol[src.y] = 1;
    
13.         for (int x = src.x + 1; x <= dst.x; x++) {
    
14.             int[] newCol = new int[height];
    
15.             for (int y = 0; y < height; y++) {
    
16.                 int topLeft = (y > 0) ? currCol[y - 1] : 0;
    
17.                 int left = currCol[y];
    
18.                 int botLeft = (y < height - 1) ? currCol[y + 1] : 0;
    
19.                 newCol[y] = topLeft + left + botLeft;
    
20.             }
    
21.             currCol = newCol;
    
22.         }
    
23.         return currCol[dst.y];
    
24.     }
    

复制代码