一個機器人位于一個 m x n 網格的左上角 （起始點在下圖中標記為“Start” ）。

機器人每次只能向下或者向右移動一步。機器人試圖達到網格的右下角（在下圖中標記為“Finish”）。

現在考慮網格中有障礙物。那么從左上角到右下角將會有多少條不同的路徑？

網格中的障礙物和空位置分別用 1 和 0 來表示。

說明：m?和 n 的值均不超過 100。

示例?1:

輸入:
[
??[0,0,0],
??[0,1,0],
??[0,0,0]
]
輸出: 2
解釋:
3x3 網格的正中間有一個障礙物。
從左上角到右下角一共有 2 條不同的路徑：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/unique-paths-ii
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

public class Solution63 {
?? ? public static int uniquePathsWithObstacles(int[][] obstacleGrid) {
?? ??? ? int i,j;
?? ??? ? int m,n;
?? ??? ? m = obstacleGrid.length;
?? ??? ? n = obstacleGrid[0].length;
?? ??? ? int[][] dp = new int[m][n];
?? ??? ? if(obstacleGrid[0][0]==1)
?? ??? ? {
?? ??? ??? ? return 0;
?? ??? ? }
?? ??? ? for(i=0;i<m;i++)
?? ??? ??? ?{
?? ??? ??? ? ? ?if(obstacleGrid[i][0]!=1)
?? ??? ??? ? ? ?{
?? ??? ??? ? ? ??? ?dp[i][0]=1;
?? ??? ??? ? ? ?}
?? ??? ? ? ??? ?if(i>0)
?? ??? ? ? ??? ?{
?? ??? ? ? ??? ??? ?dp[i][0]=dp[i-1][0]; //如果第一列存在障礙，障礙點以下的dp值都應該為0
?? ??? ? ? ??? ?}
?? ??? ??? ??? ?for(j=0;j<n;j++)
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?if(j>0&&obstacleGrid[0][j]!=1)
?? ??? ??? ??? ??? ?{
?? ??? ??? ??? ??? ? ? ? dp[0][j]=dp[0][j-1];//如果第一行存在障礙，障礙點以下的dp值都應該為0
?? ??? ??? ??? ??? ?}
?? ??? ??? ??? ??? ?if(obstacleGrid[i][j]==1)
?? ??? ??? ??? ??? ?{
?? ??? ??? ??? ??? ??? ?dp[i][j]=0;
?? ??? ??? ??? ??? ?}
?? ??? ??? ??? ??? ?if(i!=0&&j!=0&&obstacleGrid[i][j]!=1)
?? ??? ??? ??? ??? ?{
?? ??? ??? ??? ??? ??? ?dp[i][j]=dp[i][j-1]+dp[i-1][j];
?? ??? ??? ??? ??? ?}
?? ??? ??? ??? ?}
?? ??? ??? ??? ?
?? ??? ??? ?}
?? ??? ? return dp[m-1][n-1];
?? ? ? ?}
?? ? public static void main(String[] args)
?? ? {
?? ?// ?int[][] a = ?{{0,0,0},{0,1,0},{0,0,0}};
?? ??? ?int[][] a = {{0,1,0,0,0},{1,0,0,0,0},{0,0,0,0,0},{0,0,0,0,0}} ;
?? ??? ? //int[][] a = {{0,0},{0,0},{1,1}};
?? ??? ? System.out.println(uniquePathsWithObstacles(a));
?? ? }
}
?

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的动态规划--Leetcode63.不同路径二的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。