LeetCode 62. Unique Paths

Problem

LeetCode 62. Unique Paths

1. 题目简述

一个机器人坐落在一个m x n的一个网格中，初始点在top-left，终点在bottom-right，机器人只能向右或者向下走，求问有多少种走法可以到达终点。

2. 算法思路

参考解法：花花酱LeetCode

也是一道经典老题目了，DP的代表问题之一。LeetCode 63. Unique Paths II

动态规划

我们定义dp[i][j]为从[0][0]到达当前点的所有可能的方式，由于只能向右或者向下走，所以有如下递推式：

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

base case就是dp[0]和dp[i][0]，这两条边线的初始值都为1，只有一种走法。

时间复杂度:O(m * n)

空间复杂度:O(m * n)

class Solution {
    // top-down
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            Arrays.fill(dp[i], -1);
            dp[i][0] = 1;
        }
        Arrays.fill(dp[0], 1);

        return helper(dp, m - 1, n - 1);
    }

    private int helper(int[][] dp, int m, int n) {
        if (m < 0 || n < 0) {
            return 0;
        }
        if (dp[m][n] != -1) {
            return dp[m][n];
        }

        dp[m][n] = helper(dp, m, n - 1) + helper(dp, m - 1, n);

        return dp[m][n];
    }
}

class Solution {
    // bottom-up
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            Arrays.fill(dp[i], -1);
            dp[i][0] = 1;
        }
        Arrays.fill(dp[0], 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];
    }
}