• 63.不同路径 II


    原题链接

    题解

    一个简单的动态规划,除了第0行、第0列和障碍物之外的点,都是由他的上一个点和左边的一个点拓展而来
    所以当该点是障碍物:令dp[i][j] = 0(方便后面直接运算)
    当该点是(0,0)且不是障碍:dp[0][0] = 1;
    当该点是第0行的点:令dp[i][j] = dp[i][j - 1]
    当该点是第0列的点:令dp[i][j] = dp[i - 1][j]
    反之dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

    代码如下

    class Solution {
        public int uniquePathsWithObstacles(int[][] obstacleGrid) {
            int lenx = obstacleGrid.length; if(lenx == 0) return 0;
            int leny = obstacleGrid[0].length;
    
            int[][] dp = new int[101][101];
            if(obstacleGrid[0][0] == 0)//当起点是障碍物的时候,就不能走了,直接起点为0(后面就会全为0,因为所有的点都是通过起点拓展出来的)
            dp[0][0] = 1;
            for(int i = 0; i < lenx; ++i){
                for(int j = 0; j < leny; ++j){
                    if(obstacleGrid[i][j] == 0){
                        if(i - 1 >= 0) dp[i][j] += dp[i - 1][j];
                        if(j - 1 >= 0) dp[i][j] += dp[i][j - 1];
                    }
                }
            }
    
            return dp[lenx - 1][leny - 1];
        }
    }
    
  • 相关阅读:
  • 原文地址:https://www.cnblogs.com/Lngstart/p/13255360.html
  • 最新文章
  • 热门文章
一二三 - 开发者的网上家园