今天是第三十九天，只有两道动态规划的题

 

62.不同路径 

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] path = new int[m][n];
        for(int i = 0; i<m; i++){
            path[i][0] = 1;
        }
        for(int j = 0; j< n; j++){
            path[0][j] = 1;
        }
        for(int i = 1; i<m; i++){
            for(int j = 1; j<n; j++){
                path[i][j] = path[i-1][j] + path[i][j-1];
            }
        }
        return path[m-1][n-1];
        
    }
}

和走楼梯一样，记录下每一条路径的到达方法个数，然后把上面的格子和左边格子的都加起来。有边界的话要先把值设为1。

63. 不同路径 II

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int n = obstacleGrid.length;
        int m = obstacleGrid[0].length;
        if(obstacleGrid[n-1][m-1]==1||obstacleGrid[0][0]==1){
            return 0;
        }
        for(int i = 0; i<n; i++){
            for(int j = 0; j< m; j++){
                if(obstacleGrid[i][j]==1){
                    obstacleGrid[i][j] = -1;
                }
            }
        }
        obstacleGrid[0][0] = 1;
        for(int i = 1; i<n; i++){
            if(obstacleGrid[i][0]!=-1&&obstacleGrid[i-1][0]==1){
                obstacleGrid[i][0] = 1;
            }
            
        }
        for(int j = 1; j< m; j++){
            if(obstacleGrid[0][j]!=-1&&obstacleGrid[0][j-1]==1){
                obstacleGrid[0][j] = 1;
            }
            
        }
        for(int i = 1; i< n; i++){
            for(int j = 1; j< m; j++){
                if(obstacleGrid[i][j]!=-1){
                    if(obstacleGrid[i-1][j]!=-1){
                        obstacleGrid[i][j] += obstacleGrid[i-1][j];
                    }
                    if(obstacleGrid[i][j-1]!=-1){
                        obstacleGrid[i][j] += obstacleGrid[i][j-1];
                    }
                    
                }
            }
        }
        return obstacleGrid[n-1][m-1];
    }
}

和上道题一样，每个格子只有在自己本身不是障碍物和前面的格子不是障碍物的情况下，才加上前面盒子的路径

 

今天是两道medium，都不难，但是要把情况都考虑到

原文地址：http://www.cnblogs.com/catSoda/p/16907687.html

1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！ 2. 分享目的仅供大家学习和交流，请务用于商业用途! 3. 如果你也有好源码或者教程，可以到用户中心发布，分享有积分奖励和额外收入！ 4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！ 5. 如有链接无法下载、失效或广告，请联系管理员处理！ 6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！ 7. 如遇到加密压缩包，默认解压密码为"gltf",如遇到无法解压的请联系管理员！ 8. 因为资源和程序源码均为可复制品，所以不支持任何理由的退款兑现，请斟酌后支付下载 声明：如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性