动态规划：路径问题

本文对动态规划中的路径问题进行讲解，借用leetcode62、63中的两道题目。

【题目概括】 如上图，62题目的要求是我们从机器人位置走到星星位置，有多少条路线。63题中是在网格中多出了障碍物，也是问路线数。

像这种类型的题，该怎么解？很多人知道用动态规划，但是一到去做，就无从下手。

对于62题目，我是这样想的：机器人从（0，0）出发到（m-1，n-1）共有多少种路线（机器人只能向右向下走）。我们可以通过下面几步来进行分析：

• 首先确定dp数组及其下标的含义。dp[i][j]表示从（0，0）到（i，j）共有dp[i][j]种路径。
• 确定递推公式。因机器人只能向右走和向下走，故要求dp[i][j]，只能从左侧dp[i][j-1]和上侧dp[i-1][j]两个方向来推导。那么很显然dp[i][j] = dp[i-1][j] + dp[i][j-1]。
• dp数组的初始化。第一行dp[0][j]和第一列dp[i][0]肯定都只有一条路线（从（0，0）到（i，0）或（0，j）的路径只有一条），所以初始化代码： for (int i = 0; i < m; i++) dp[i][0] = 1; for (int j = 0; j < n; j++) dp[0][j] = 1; 确定遍历顺序。从左到右一层一层遍历就行了。思路理解之后，代码就变得清晰易写了。再用到类似的问题，我们依然可以用这样的分析思路。 代码如下：

    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n]; //dp[i][j]表示[0，0]到[i,j]有多少路径
        for (int i = 0; i < m; i++) dp[i][0] = 1;
        for (int j = 0; j < n; j++) dp[0][j] = 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];
    }

我们按照前面的思路，对应到63题该怎么做呢？慢慢来依然是那几步。

• 确定dp数组及其下标的含义。dp[i][j]表示从（0，0）到（i，j）共有dp[i][j]种路径。

• 确定递推公式。因机器人只能向右走和向下走，故要求dp[i][j]，只能从左侧dp[i][j-1]和上侧dp[i-1][j]两个方向来推导。那么很显然dp[i][j] = dp[i-1][j] + dp[i][j-1]。

• dp数组的初始化。初始化[0][j]和[i][0]也就是第一行第一列，如果行或列上遇到了障碍物，那从障碍物开始到行列结束都是访问不到的。所以初始化列代码如下，行代码同理。

    for (int i = 0; i < m; i++) {
        if(obstacleGrid[i][0] == 0){
            dp[i][0] = 1;//无障碍
        }else {//否则障碍后这一列都到不了
            while(i < m){
                dp[i++][0] = 0;
            }
        }
    }
  

• 确认遍历顺序，从左到右就行。我们需要分成两种情况，当前位置是否是障碍，如果是路障的话，没有路径可达，dp[i][j]直接记为0.若不是路障又需要考虑左侧有障碍上侧无障碍、左侧无障碍上侧有障碍、左上都有障碍、左上都无障碍四种情况。 代码：

    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            if(obstacleGrid[i][0] == 0){
                dp[i][0] = 1;//无障碍
            }else {//否则障碍后这一列都到不了
                while(i < m){
                    dp[i++][0] = 0;
                }
            }
        }
        for (int j = 0; j < n; j++) {
            if(obstacleGrid[0][j] == 0){
                dp[0][j] = 1;
            }else {
                while(j < n){
                    dp[0][j++] = 0;
                }
            }
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if(obstacleGrid[i][j] == 1){//当前位置是路障
                    dp[i][j] = 0;
                }else{
                    //当前位置不是路障
                    //不在第一行第一列的路障
                    if(dp[i-1][j] == 0 && dp[i][j-1] !=0){
                        //路障在（i,j）上方（行上）
                        dp[i][j] = dp[i][j-1];
                    } else if (dp[i][j-1] == 0 && dp[i-1][j] !=0) {
                        //路障在(i,j)左方(列上)
                        dp[i][j] = dp[i-1][j];
                    } else if (dp[i-1][j] == 0 && dp[i][j-1] == 0) {
                        //行列都有路径(i,j)左方上方都有路障
                        dp[i][j] = 0;
                    } else if (dp[i-1][j] != 0 && dp[i][j-1] != 0) {
                        //无路障
                        dp[i][j] = dp[i-1][j] + dp[i][j-1];
                    }
                }
            }
        }

        return dp[m-1][n-1];
    }