Unique Paths II -- LeetCode

 
這道題跟Unique Paths非常類似，只是這道題給機器人加了障礙，不是每次都有兩個選擇（向右，向下）了。因為有了這個條件，所以Unique Paths中最後一個直接求組合的方法就不適用了，這裡最好的解法就是用動態規劃了。遞推式還是跟Unique Paths一樣，只是每次我們要判斷一下是不是障礙，如果是，則res[i][j]=0，否則還是res[i][j]=res[i-1][j]+res[i][j-1]。實現中還是只需要一個一維數組，因為更新的時候所需要的信息足夠了。這樣空間復雜度是是O(n)（如同Unique Paths中分析的，如果要更加嚴謹，我們可以去行和列中小的那個，然後把小的放在內層循環，空間復雜度就是O(min(m,n))，時間復雜度還是O(m*n)。代碼如下：

public int uniquePathsWithObstacles(int[][] obstacleGrid) {
    if(obstacleGrid == null || obstacleGrid.length==0 || obstacleGrid[0].length==0)
        return 0;
    int[] res = new int[obstacleGrid[0].length];
    res[0] = 1;
    for(int i=0;i0)
                    res[j] += res[j-1];
            }
        }
    }
    return res[obstacleGrid[0].length-1];
}