[アルゴリズムの問題を解く]プログラマーの通学路

昨日寝る前にできた問題!久しぶりにコーテの前にDPを解いた気がして感覚を探して解けました!
この問題はプログラマーの高得点スイートの動的プログラミング分類の中のlevel 3問題です!
https://programmers.co.kr/learn/courses/30/lessons/42898

問題の説明

持続的な豪雨が一部の地域を水没させた.水没していない地域を通って学校に行きたいです.家から学校までの道はm×nサイズのグリッドで表すことができます.
下図はm=4,n=3である.

最左上隅(すなわち家屋の所在地の座標)は(1,1)であり、最右下角(すなわち学校の所在地の座標)は(m,n)である.
グリッドサイズm、n、および水没領域座標を含む2 Dフラットピットにパラメータ化します.右側と下側だけに移動し、家から学校までの最短パスの数を1000000 7で割ってからソリューション関数に戻ってください.

せいげんじょうけん

メッシュのサイズはm,nは1または100以下の自然数である.

mとnがともに1の場合、入力は提供されません.

水没した地域は10を超えない.

家や学校が水没した場合は、入力としません.

I/O例

mnpuddlesreturn43[[2, 2]]4

解答方法

これは典型的なDP問題であり、各セルが達成できるメソッドの数を格納し、これらの値を利用して他のセルが達成できるメソッドの数をエクスポートします.
この問題では,学校(1,1)>(m,n)への最短経路を導出するので,右と下への移動を考慮するだけでよい.そこで、始点を1、水たまりを-1、初期値を0として探索し、水たまりがあるセルを処理し、左側と上に格納されているパス数を加算して、各セルに到達するパス数を算出します.
本人は,二重forゲート内で無意味な条件判別を継続することを避けるために,(1,1)を単独割当て(0,1)ではなく,(1,1)に指定し,二重forゲート内の論理に基づいて,(1,1)を1に指定する.

コード#コード#

public class Solution {
    private static final int divider = 1000000007;
    public static int solution(int m, int n, int[][] puddles) {
        int[][] dp = new int[n+1][m+1];
        for (int[] puddle : puddles) dp[puddle[1]][puddle[0]] = -1;
        dp[0][1] = 1;
        for(int i=1; i<=m; i++){
            for(int j=1; j<=n; j++){
                if (dp[j][i] == -1) dp[j][i] = 0;
                else dp[j][i] = (dp[j-1][i] + dp[j][i-1])%divider;
            }
        }
        return dp[n][m];
    }
}