网站建设官方网站,网站模板怎么制作,如何做网页图片,自贡在线最新消息思路 典型的DP问题#xff0c;状态转换方程为dp[i][j]dp[i-1][j]dp[i][j-1],边界情况单独讨论
解题方法 对于第一行#xff1a;如果当前元素为0且在该元素的同一行的左边不存在1#xff0c;则路径数皆为1#xff0c;否则为零 对于第一列#xff1a;如果当前元素为0且在该…
思路 典型的DP问题状态转换方程为dp[i][j]dp[i-1][j]dp[i][j-1],边界情况单独讨论
解题方法 对于第一行如果当前元素为0且在该元素的同一行的左边不存在1则路径数皆为1否则为零 对于第一列如果当前元素为0且在该元素的同一列的上边不存在1则路径数皆为1否则为零 对于其他元素的路径数则按状态转换方程进行计算 最后返回dp[m-1][n-1]即可
Code
class Solution {public int uniquePathsWithObstacles(int[][] obstacleGrid) {int mobstacleGrid.length;int nobstacleGrid[0].length;int ans[][]new int[m][n];boolean flagtrue;for(int i0;in;i){if(obstacleGrid[0][i]0flag)ans[0][i]1;if(obstacleGrid[0][i]1||!flag){ans[0][i]0;flagfalse;}}flagtrue;for(int i0;im;i){if(obstacleGrid[i][0]0flag)ans[i][0]1;if(obstacleGrid[i][0]1||!flag){ans[i][0]0;flagfalse;}}for(int i1;im;i){for(int j1;jn;j){if(obstacleGrid[i][j]!1){ans[i][j]ans[i-1][j]ans[i][j-1];}else{ans[i][j]0;}}}return ans[m-1][n-1];}}
