62. Unique Paths

机器人只能走右边或者下边，问在m行n列的矩阵中从左上角走到右下角一共有几种走法。

1.递归解法，考虑右下角坐标m - 1，n - 1的走法为它上边m - 2, n - 1和左边m - 1, n - 2走法之和，也就是dfs(m, n) = dfs(m - 1, n) + dfs(m, n - 1)，边界返回一种走法。递归超时41 / 62 test cases passed.(m = 51, n = 9)

public int uniquePaths(int m, int n) {
    if (m <= 0 || n <= 0) return 0; // deal with negative boundary
    return dfs(m - 1, n - 1);
}

public int dfs(int m, int n) {
    if (m == 0 || n == 0) return 1;
    return dfs(m - 1, n) + dfs(m, n - 1);
}

2.memorization，在函数调用的时候添加缓存，递归的同时查找缓存

public int uniquePaths(int m, int n) {
    if (m <= 0 || n <= 0) return 0;
    int[][] memo = new int[m][n];  // memo here
    return dfs(m - 1, n - 1, memo);
}

public int dfs(int m, int n, int[][] memo) {
    if (m == 0 || n == 0) return 1;
    if (memo[m][n] == 0) { // if memo does not record any value
        memo[m][n] = dfs(m - 1, n, memo) + dfs(m, n - 1, memo);
    }
    return memo[m][n];
}

3.dp, dp数组边界都为1（都只有一种走法），O(mn)

public int uniquePaths(int m, int n) {
    if (m <= 0 || n <= 0) return 0;
    int[][] dp = new int[m][n];
    // for (int[] row : dp) Arrays.fill(row, 1); // or fill all elements with 1...
    for (int i = 0; i < m; i++) {
       dp[i][0] = 1;
    }
    for (int i = 0; i < n; i++) {
       dp[0][i] = 1;
    }
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }
    return dp[m - 1][n - 1];
}