62. Unique Paths

https://leetcode.com/problems/unique-paths/

注意本题只能向右 / 向上走。

DP 问题，经典又熟悉。

暴力递归->傻缓存->动态规划。

class Solution {
    int M, N;

    public int uniquePaths(int m, int n) {
        M = m;
        N = n;
        // Approach 1: Recursive, Brute Force
// return process1(0, 0);

        // Approach 2: Recursion with Memoization
// int[][] dp = new int[M][N];
// dp[M - 1][N - 1] = 1;
// return process2(0, 0, dp);

        // Approach 3: Dynamic Programming
        int[][] dp = new int[M][N];
        for (int i = M - 1; i >= 0; i--) {
            dp[i][N - 1] = 1;
        }
        for (int j = N - 1; j >= 0; j--) {
            dp[M - 1][j] = 1;
        }
        for (int i = M - 2; i >= 0; i--) {
            for (int j = N - 2; j >= 0; j--) {
                dp[i][j] = dp[i + 1][j] + dp[i][j + 1];
            }
        }
        return dp[0][0];
    }

// public int process2(int i, int j, int[][] dp) { // 从i,j到M,N共有多少种路径
// if (i == M || j == N) return 0;
// if (dp[i][j] > 0) return dp[i][j];
// dp[i][j] = process2(i + 1, j, dp) + process2(i, j + 1, dp);
// return dp[i][j];
// }

// public int process1(int i, int j) {
// if (i == M || j == N) return 0;
// if (i == M - 1 && j == N - 1) return 1;
// return process1(i + 1, j) + process1(i, j + 1);
// }
}

63. Unique Paths II

https://leetcode.com/problems/unique-paths-ii/

DP 问题，同上题，注意本题只能向右 / 向上走，只不过多了一些障碍物。
暴力递归->傻缓存->动态规划。

class Solution {
    int M, N;

    public int uniquePathsWithObstacles(int[][] grid) {
        M = grid.length;
        N = grid[0].length;
        // Approach 1: Recursive, Brute Force
// return process1(0, 0, grid);

        // Approach 2: Recursion with Memoization
        // int[][] dp = new int[M][N];
        // for (int i = 0; i < M; i++) {
        // Arrays.fill(dp[i], -1);
        // }
        // dp[M - 1][N - 1] = 1 - grid[M - 1][N - 1];
        // for (int i = M - 2; i >= 0; i--) {
        // if (grid[i][N - 1] == 1 || dp[i + 1][N - 1] == 0) dp[i][N - 1] = 0;
        // else dp[i][N - 1] = 1;
        // }
        // for (int j = N - 2; j >= 0; j--) {
        // if (grid[M - 1][j] == 1 || dp[M - 1][j + 1] == 0) dp[M - 1][j] = 0;
        // else dp[M - 1][j] = 1;
        // }
        // return process2(0, 0, grid, dp);

        // Approach 3: Dynamic Programming
       int[][] dp = new int[M][N];
       dp[M - 1][N - 1] = 1 - grid[M - 1][N - 1];
       for (int i = M - 2; i >= 0; i--) {
           if (grid[i][N - 1] == 1 || dp[i + 1][N - 1] == 0) dp[i][N - 1] = 0;
           else dp[i][N - 1] = 1;
       }
       for (int j = N - 2; j >= 0; j--) {
           if (grid[M - 1][j] == 1 || dp[M - 1][j + 1] == 0) dp[M - 1][j] = 0;
           else dp[M - 1][j] = 1;
       }
       for (int i = M - 2; i >= 0; i--) {
           for (int j = N - 2; j >= 0; j--) {
               if (grid[i][j] == 1) dp[i][j] = 0;
               else dp[i][j] = dp[i + 1][j] + dp[i][j + 1];
           }
       }
       return dp[0][0];
    }

// public int process2(int i, int j, int[][] grid, int[][] dp) { // 从i,j到M,N共有多少种路径
// if (i == M || j == N || grid[i][j] == 1) return 0;
// if (dp[i][j] >= 0) return dp[i][j];
// dp[i][j] = process2(i + 1, j, grid, dp) + process2(i, j + 1, grid, dp);
// return dp[i][j];
// }

// public int process1(int i, int j, int[][] grid) {
// if (i == M || j == N || grid[i][j] == 1) return 0;
// if (i == M - 1 && j == N - 1) return 1;
// return process1(i + 1, j, grid) + process1(i, j + 1, grid);
// }
}

980. Unique Paths III

https://leetcode.com/problems/unique-paths-iii/

本题是有史以来做过的最简单的 hard 了，就是一个没有任何优化技巧的 backtracing，30分钟搞定。

思路如下：因为 exactly once 语义，所以不能走重复路线，故维护一个 visited 数组。另外维护一个 remain 代表剩余步数，当经过终点时，看剩余步数是否恰好为0，或者当剩余步数为 0 时，看是否恰好经过终点。否则没有必要继续走下去。

class Solution {
    int M, N;
    int startX, startY;
    int endX, endY;

    public int uniquePathsIII(int[][] grid) {
        M = grid.length;
        N = grid[0].length;
        int remain = M * N;
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                if (grid[i][j] == -1) remain--;
                if (grid[i][j] == 1) {
                    startX = i;
                    startY = j;
                } else if (grid[i][j] == 2) {
                    endX = i;
                    endY = j;
                }
            }
        }

        boolean[][] visited = new boolean[M][N];
        return process(startX, startY, grid, visited, remain - 1);
    }

    // 剩余remain步，从i,j到endX, endY共有多少种路径
    public int process(int i, int j, int[][] grid, boolean[][] visited, int remain) {
        if (i < 0 || i == M || j < 0 || j == N || visited[i][j] || grid[i][j] == -1) return 0;
        if (remain == 0 || i == endX && j == endY) return remain == 0 && i == endX && j == endY ? 1 : 0;

        visited[i][j] = true;
        int p1 = process(i - 1, j, grid, visited, remain - 1);
        int p2 = process(i + 1, j, grid, visited, remain - 1);
        int p3 = process(i, j - 1, grid, visited, remain - 1);
        int p4 = process(i, j + 1, grid, visited, remain - 1);
        visited[i][j] = false;
        
        return p1 + p2 + p3 + p4;
    }
}