leetcodeライブラリ--63別経路II

別のパスは、この問題は組み合わせの問題です.

int fun(int num)
    {
        int ans = 1;
        while(num)
        {
            ans*=num;
            num--;
        }

        return ans;
    }
    int uniquePaths(int m, int n) {
        
        int all = m+n-2;
        int ans = fun(all)/fun(m-1)/fun(all-m+1);
        
        return ans;
    }

63異なる経路IIのロボットは、m x nグリッドの左上に位置しています.(スタートポイントは下図の「Start」と表記されています.)
ロボットは下か右にしか動かない.ロボットはグリッドの右下に到達しようとします.
グリッド内に障害物があると考えます.左上から右下まではいくつのルートがありますか?
考え:この問題は典型的な動的計画問題で、dp[i＋1][j＋1]で第i行j列に到達するにはいくつかの走法があると表しています.状態移動方程式も書きやすいです.各格の位置に到達するには二つの方法しかありません.上から下へ、または左から右へ.dp[i＋1][j＋1]=dp[i]、[j＋1]+dp[i＋1][j]開始にはdp[0][1]=1が必要です.最初の席に行くには歩き方があるからです.
ここでは、すべての結果を保存するための配列を使用していますが、実際には、各位置は前の行とこの行の新しい情報だけを見ることができます.したがって、一次元配列だけでいいです.
似たテーマ:階段を歩く(一次元の)

int m = obstacleGrid.size();
int n = obstacleGrid[0].size();
vector> dp(m+1, vector(n+1, 0));

dp[0][1] = 1;

for(int i = 0; i < m; ++i)
{
    for(int j = 0; j < n; ++j)
    {
        if(obstacleGrid[i][j]  == 0)
        {
            dp[i+1][j+1] = dp[i][j+1] + dp[i+1][j];
        }
    }
}

return dp[m][n];

)