【DP】 - Unique Paths

Given a grid[][], one can only move either right, right up or right down at any point in time, how many paths are there to start from top left corner and stop at top right corner?

class Solution {
    public int getNumOfPaths(int[][] grid) {
        if (grid == null || grid.length == 0) {
            return -1;
        }
      
        // dynamic programming
        int[][] paths = new int[grid.length][grid[0].length];
        paths[0][0] = 1;
        for (int i = 1; i < grid.length; i++) {
            paths[i][0] = 0;
        }

        for (int i = 0; i < grid.length; i++) {
            for (int j = 1; j < grid[0].length; j++) {
                if (i == 0) {
                    paths[i][j] = paths[i][j - 1] + paths[i + 1][j - 1];
                    continue;
                }

                paths[i][j] = paths[i][j - 1] + paths[i - 1][j - 1] + paths[i + 1][j - 1];
            }
        }
    } // end of for
    return paths[0][grid[0].length - 1];
}

Follow-up 1:

If three points of the grid are given, what is the result if it is asked to go through all these points.

Since one can only go from left to right, we could sort the given points in ascending order of j (from left to right), and go to each of the point in order, finally arrive at right top corner.

class Solution {

    int[][] paths;

    public getPaths(int[][] grid, int[] p1, int[] p2, int[] p3) {
        if (grid == null || grid.length == 0) {
            return -1;
        }

        int[][] points = new int[][]{{0, 0}, p1, p2, p3, {0, grid[0].length - 1}};
        Arrays.sort(points, Comparator.comparing((int[] arr) -> arr[1]));

        paths = new int[grid.length][grid[0].length];
        paths[0][0] = 1;
        for ( int i = 0; i < 4; i++) {
            getNumOfPaths(grid, points[i] , points[i + 1]);
        }

        return paths[0][grid[0].length - 1];
    }

    private void getNumOfPaths(int[][] grid, int[] s, int[] e) {
        // clear other paths on the same column with p1
        for (int i = 0; i < grid.length; i++) {
           if (i == s[0]) {
               continue;
           }
            paths[i][s[1]] = 0;
        }

        for (int i = 0; i < grid.length; i++) {
            for (int j = s[1] + 1; j <= e[1]; j++) {
                if (i == 0) {
                    paths[i][j] = paths[i][j - 1] + paths[i + 1][j - 1];
                    continue;
                }

                paths[i][j] = paths[i][j - 1] + paths[i - 1][j - 1] + paths[i + 1][j - 1];
            }
        }  // end of for
    }
}

Follow-up 2:

How to know if there can be any possible paths satisfy follow-up 1?

1. Any two of the five points {{0, 0}, p1, p2, p3, {0, grid[0].length - 1}} should not have the same p[1];
2. If any two points e.g. p1, p2 from the five points have |p1[1] - p2[1]| == 1, then |p1[0] - p2[0]| should also be 1.

Follow-up 3:

Given an H, make sure your path go beyond H to its down.

以h为对称轴，将右上角的点作关于h的轴对称。