11/7 <Dynamic Programming>

62. Unique Paths

方法一：二位数组

而这道题是每次可以向下走或者向右走，求到达最右下角的所有不同走法的个数。那么跟爬梯子问题一样，需要用动态规划 Dynamic Programming 来解，可以维护一个二维数组 dp，其中 dp[i][j] 表示到当前位置不同的走法的个数，然后可以得到状态转移方程为: dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

class Solution {

    public int uniquePaths(int m, int n) {

        int[][] result = new int[m][n];

        for(int i = 0; i < m; i++){

            for(int j = 0; j < n; j++){

                if(i == 0 || j == 0)

                    result[i][j] = 1;

                else

                    result[i][j] = result[i - 1][j] + result[i][j - 1];

            }

        }

        return result[m - 1][n - 1];

    }

}

方法二：

为了节省空间，实际上我们只需要记录遍历到(i, j)这个位置的时候当前行有几种路径,如果遍历到(i, m-1)的时候,替换掉这一行对应列的路径即可，于是状态转移方程编程:
dp[j] = dp[j] + dp[j-1]

class Solution {

    public int uniquePaths(int m, int n) {

        int[] dp = new int[n];

        dp[0] = 1;

        for(int i = 0; i < m; i++){

            for(int j = 1; j < n; j++){

                dp[j] += dp[j-1];

            }

        }

        return dp[n-1];

    }

}

63. Unique Paths II

如果有障碍，则dp[j] = 0;

class Solution {

    public int uniquePathsWithObstacles(int[][] obstacleGrid) {

        int width = obstacleGrid[0].length;

        int[] dp = new int[width];

        dp[0] = 1;

        for(int[] row : obstacleGrid){

            for(int j = 0; j < width; j++){

                if(row[j] == 1)

                    dp[j] = 0;

                else if(j > 0)

                    dp[j] += dp[j - 1];

            }

        }

        return dp[width - 1];

    }

}

巴特西

11/7 <Dynamic Programming>

最新文章

热门文章