本文主要是介绍day39||第九章 动态规划part02,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
62.不同路径
class Solution {public int uniquePaths(int m, int n) {int[][] dp = new int[m][n];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. 不同路径 II
一开始把题想复杂了。还想着把问题分解,先走到障碍附近,然后接着走,其实就把dp对应的位置置零就行了。。。。
我们已经详细分析了没有障碍的情况,有障碍的话,其实就是标记对应的dp table(dp数组)保持初始值(0)就可以了。还有就是初始化,要注意障碍出现在起始行和起始列的情况。
class Solution {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 && obstacleGrid[i][0]==0;i++) dp[i][0] = 1;for(int j =0;j<n && obstacleGrid[0][j]==0;j++) dp[0][j] = 1;for(int i =1;i<m;i++){for(int j = 1;j<n;j++){if(obstacleGrid[i][j]==0){dp[i][j] = dp[i-1][j]+dp[i][j-1];}}}return dp[m-1][n-1];}
}
这篇关于day39||第九章 动态规划part02的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!