[プログラマー]通学路

14673 ワード
テキストリンク
リンク:https://programmers.co.kr/learn/courses/30/lessons/42898#
この問題はDPでなくても、子供の頃退屈だったときに本の隅に解答を描いていたよくある問題です.

右と下にしか移動しないので、DPは可能です.
したがって、動的プログラミングを実行するためにdp[i][j] = dp[i-1][j] + dp[i][j-1]の方法を確立することができる.
この場合、支店と列を正しく区切ってこそ、時間の無駄を減らすことができます.
△実施問題には常に注意しなければならない.

前提条件


このため,(1,1)1つのパスしかないと仮定すると,(i,1),(1,j)ともに1つのパスしかない.

私が書いたコード

#include <string>
#include <vector>

using namespace std;
int map[101][101];
long long dp[101][101];
int solution(int m, int n, vector<vector<int>> puddles) {
    
    for(int i = 0;i < puddles.size();i++){
        map[puddles[i][1]][puddles[i][0]] = -1;
    }
    dp[1][1] = 1;
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= m;j++){
            if(i == j && i == 1) continue;
            if(map[i][j] != -1){
                dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % 1000000007;   
            }
        }
    }
    return dp[n][m];
}

サンプルコード


サンプルコードは、私が作成したコードよりも効率的です.
他の部分は私のコードと似ていますが、if文に3つの演算子が適用されています.
感嘆して感嘆する.for (int c = r != 1 ? 1 : 2; c <= m; ++c) 
#include <string>
#include <vector>
#include <set>
using namespace std;

int solution(int m, int n, vector<vector<int>> puddles) {
    int answer = 0;
    vector<vector<int>> cnt(n + 1, vector<int>(m + 1, 0));
    set<pair<int, int>> pChk;
    cnt[1][1] = 1;
    for (int i = 0; i < puddles.size(); ++i)
    {
        pChk.insert({ puddles[i][1], puddles[i][0] });
    }
    for (int r = 1; r <= n; ++r)
    {
        for (int c = r != 1 ? 1 : 2; c <= m; ++c)
        {
            if (pChk.find({ r, c }) == pChk.end())
                cnt[r][c] = (cnt[r - 1][c] + cnt[r][c - 1]) % 1000000007;
        }
    }
    answer = cnt[n][m];
    return answer;
}

注意点


まず,よくある実装問題のように配列のインデックスに注意する.
i,jのようなインデックスと行と列はよく一致しなければならない.
プログラマ-N個最小公倍数
16号-バックグラウンド追跡-研究所(三星電子)