[C++]LeetCode: 78 Unique Paths II

タイトル:
Follow up for "Unique Paths":
Now consider if some obstacles are added to the grids. How many unique paths would there be?
An obstacle and empty space is marked as  1  and  0  respectively in the grid.
For example,
There is one obstacle in the middle of a 3x3 grid as illustrated below.

[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]

The total number of unique paths is  2 .
Note: m and n will be at most 100.
考え方:この問題はLeetCode:56 Unique Pathsとよく似ていますが、今回はまず障害があるかどうかを判断します.毎回2つの選択肢(右、下)があるわけではありません.これがあったので、私たちは直接結果を求めることができません.繰返し式はunique pathと同じですが、私たちは毎回障害があるかどうかを判断しなければなりません.もしあれば、dp[i][j]=0、dp[i][j]=dp[i-1][j]+dp[i][j-1].だから、実際には更新時の情報で十分なので、1次元配列しか必要ありません.
Attention: 1. 注意unique pathとの違いは,まず1次元配列の初期化であり,第1行に障害があるか否かを判断する必要があるため,初期化時は0である.

<span style="font-size:14px;">vector<int> dp(col, 0);</span>

2.第1行目のdp値を算出する必要があるため、ループ範囲は0~row,0~colである.再帰式を算出する場合、dp[ci]=dp[ci]+dp[ci-1]であり、ci>0を先に判断することに注意する.

<span style="font-size:14px;">for(int ri = 0; ri < row; ri++)
        {
            for(int ci = 0; ci < col; ci++)
            {</span>

3.dp[0]を初期化する必要があります.obstacleGrid[0][0]=1の場合、dp[0]を0にリセットします.そうしないと、dp[0]=1は、次のダイナミックプランニングテーブルの値を更新するために使用されます.

<span style="font-size:14px;">if(obstacleGrid[ri][ci] == 1)
{
   dp[ci] = 0;
}
else
{
   if(ci > 0)
   dp[ci] = dp[ci] + dp[ci-1];
}</span>

複雑度:時間複雑度,一次遍歴O(n),空間複雑度,一次元配列,O(N)
AC Code:

<span style="font-size:14px;">class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
        int row = obstacleGrid.size();
        int col = obstacleGrid[0].size();
        if(row == 0 || col == 0) return 0;
        
        vector<int> dp(col, 0);
        dp[0] = 1;
        
        for(int ri = 0; ri < row; ri++)
        {
            for(int ci = 0; ci < col; ci++)
            {
                if(obstacleGrid[ri][ci] == 1)
                {
                    dp[ci] = 0;
                }
                else
                {
                    if(ci > 0)
                        dp[ci] = dp[ci] + dp[ci-1];
                }
            }
        }
        
        return dp.back();
    }
};</span>