java LeetCode題解不同路徑

更新時間：2023年06月15日 15:16:02 作者：搬碼人

這篇文章主要為大家介紹了java LeetCode題解不同路徑示例，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪

題目描述

一個機器人位于一個m×n網(wǎng)格的左上角。

機器人每次只能向下或者向右移動一步。機器人試圖到達網(wǎng)格的右下角。

現(xiàn)在考慮網(wǎng)格中有障礙物。那么從左上角到右下角將會有多少條不同的路徑呢？

網(wǎng)格中的障礙物和空位置分別用1和0表示。

示例

來自LeetCode

輸入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]

輸出：2

解釋：3x3 網(wǎng)格的正中間有一個障礙物。

從左上角到右下角一共有 2 條不同的路徑：

向右 -> 向右 -> 向下 -> 向下
向下 -> 向下 -> 向右 -> 向右

方法思路

同前面的不同路徑解法一樣，最優(yōu)方法是采用動態(tài)規(guī)劃。

此處同時采用滾動數(shù)組優(yōu)化空間。

我們用f(i,j)來表示從坐標(0,0)到坐標(i,j)的路徑數(shù)，u(i,j)表示坐標(i,j)是否可行，如果坐標(i,j)有障礙物，u(i,j)=0，否則u(i,j)=1。

因為機器人只能向下或者向右移動，所以坐標(0,0)到坐標(i,j)的路徑總數(shù)的值只能取決于坐標(0,0)到坐標(i-1,j)的路徑總數(shù)和從坐標(0,0)到坐標(i,j-1)的路徑總數(shù)，即f(i,j)只能通過f(i-1,j)和坐標f(i,j-1)轉移得到。當坐標(i,j)本身有障礙物的時候，

任何路徑都到不了f(i,j)，此時f(i,j)=0。

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int n = obstacleGrid.length;
        int m = obstacleGrid[0].length;
        int[] f = new int[m];
        f[0]= obstacleGrid[0][0]==0?1:0;
        for(int i=0;i<n;++i){
            for(int j=0;j<m;++j){
                if(obstacleGrid[i][j]==1){
                    f[j]=0;
                    continue;
                }
                if(j>=1&&obstacleGrid[i][j-1]==0){
                    f[j]+=f[j-1];
                }
            }
        }
        return f[m-1];
    }
}

復雜度分析