题解 | #求路径#

NC34 求路径

题目思路：这道题目其实很一道很经典的动态规划题目，题目意思很好理解，就是找从起点到终点的所有可行的路径。

约束的两个条件：

• 机器人每次只能往右或者往下走
• 机器人不能越界

我们看到这张图就明白一切：

方法一：经典使用dp数组

有了上面的两个条件，我们就可以解决这个题目了。

我们定义一个二维dp数组，dp[i] [j] 表示从起点到我当前位置（i行j列）有多少条可行的路径，因为我们从约束条件中可以知道，机器人每次只能往右或者往下走，则我们当前点必定是从上面或者左边走过来的（除边界外）。

当然，如果在地图的最上面或者最左边的话，最上面的点只能是从左边走到的，最左边的点只能是从上面走到的。

则我们可以定义状态方程：

当 i > 1 && j > 1 : dp[i] [j] = dp[i] [j-1] + dp[i-1] [j]

当 i = 0：dp[0] [j] = dp[0] [j-1]

当 j = 0：dp[i] [0] = dp[i-1] [0]

所以我们可以写出代码：

public int uniquePaths (int m, int n) {
        // 定义dp数组
        int[][] dp = new int[m][n];

        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                // 当 i = 0：dp[0][j] = dp[0][j-1]
                if(i == 0){
                    dp[i][j] = 1; // 都是1是因为dp[0][j] = dp[0][j-1]，所以干脆全部赋值为1
                    continue;
                }
                // 当 j = 0：dp[i][0] = dp[i-1][0]
                if(j == 0){
                    dp[i][j] = 1;
                    continue;
                }
                // 当 i > 1 && j > 1 :  dp[i][j] = dp[i][j-1] + dp[i-1][j]
                dp[i][j] = dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[m-1][n-1]; // 返回到达终点的所有可行路径
    }

方法二：递归

上面的方法是用一个dp数组来存储的，但是代码量是不是有点多，其实我们也可以用递归来实现动态规划，具体看下面的代码：

public int uniquePaths (int m, int n) {
        // 起点（1，1） 这里为什么是（1，1）呢？其实是一样的，我们上面的方法定义了（0，0）为起点，那么终点就为（m-1，n-1）
        // 这里起点为（1，1）那么终点就为 （m，n）
        if(m == 1 || n == 1)
            return 1;
        // 终点（m，n）
        return uniquePaths(m,n-1)+uniquePaths(m-1,n);
    }

我们看到上面的代码，是不是也很容易理解，主要是代码量非常的少，并且代码的可读性也提升了。

我们可以看到 uniquePaths(m,n-1)+uniquePaths(m-1,n)符合了我们的状态方程。

复杂度分析：

时间复杂度O(n²)：计算的时候，双重循环

空间复杂度O(n²)：二维数组的空间。