题解 | #求路径#

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

约束的两个条件：

机器人每次只能往右或者往下走
机器人不能越界
我们看到这张图就明白一切：
从起点1开始 当i>1 j>1时, 到达第2行第2列的格子有2种路径, 第2行第3列有3中路径....

方法一：经典使用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]

import java.util.*;


public class Solution {
    /**
     * 
     * @param m int整型 
     * @param n int整型 
     * @return int整型
     */
    public int uniquePaths (int m, int n) {

        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) {
                    // 都是1是因为dp[0][j] = dp[0][j-1]，所以干脆全部赋值为1
                    dp[i][j] = 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][j-1] + dp[i-1][j];
            }
        }

        // 返回到达终点的所有可行路径
        return dp[m-1][n-1];
    }
}