[プログラマー]通学路

コードテスト練習-通学路
水没していない地域を通って学校に行きたい.
始点(セット):(1、1)
学校:(m,n)
移動いどう:右および下のみいどう
最短パス数を10000007で割った残りのパス数を返します.

問題を理解する

いいえ.💥💥 こうしメッシュが乱れている
mxnメッシュ形状と言って、学校の位置は(4,3)...
普通mxnの時mこのrowこのnはcolがここにいる💥💥非常に注意しなければならないのは、反対です.
わあ、だから水たまりも注意して逆さにあげます.

問題を解く

この問題もサブ問題に分けることができる.すなわち,動的計画法の問題である.
現在(1,1)→(m,n)を求めているが,その間の[a,b]はマルチパスの道である可能性がある.

従って、[r,c]から[M−1,n−1]までの最短経路の個数を記憶するdp[r][C]が配置される.

public int recur(int r, int c){
	if( r>m-1 || c>n-1) return 0; // out of range
	if( dp[r][c] == -2 ) return 0; // 물웅덩이 - board를 따로 두지 말자.
	if( dp[r][c] != -1 ) return dp[r][c]; // 이미 풀어진 subproblem
	if( r == m -1 && c == n-1) return 1; 
	return dp[r][c] = recur(r+1,c) + recur(r,c+1);

この問題は、移動は「右」と「下」のみが許可されているため、問題が非常に容易になる->「移動可能であっても経路が最も短い」ためである.

ってどういう意味なんでしょうか、左上隅も移動できれば最終的には回り道になることもありますし、ここではそういうことを考える必要はないので.

その後、int range範囲の値が引き続き現れるように、100000007に分割された残りの部分を返す必要があります.
もちろん、これを実現するには、再帰関数ごとに返される中間結果値にmoduloを指定し、これらの値を追加した後にmoduloを指定する必要があります.

import java.util.*;
class Solution {
    public int[][] dp = new int[100][100];
    public int gm,gn;
    public int DIVIDER = 1_000_000_007;
    public int solution(int m, int n, int[][] puddles) {
        int answer = 0;
        
        gm = m; gn = n;
        // dp 세팅
        for(int r=0;r<n;r++){
            Arrays.fill(dp[r],-1);
        }
        for(int[] p : puddles){
            // p[0]은 r, p[1]은 c
            dp[p[1]-1][p[0]-1] = -2; 
        }
        // solve
        answer = recur(0,0);
        // print();
        
        return answer;
    }
    public void print(){
        for(int r =0;r<gn;r++){
            for(int c = 0 ; c<gm;c++){
                System.out.print(dp[r][c]+" ");
            }
            System.out.println();
        }
    }
    public int recur(int r, int c){
        if( r > gn-1 || c > gm-1)return 0; // out of range
        if(dp[r][c] == -2 )return 0; // 물웅덩이
        if(dp[r][c] != -1) return dp[r][c]; // solved problem 
        if(r == gn-1 && c == gm-1) return 1;
        return dp[r][c] = (recur(r+1,c) % DIVIDER + recur(r,c+1) % DIVIDER ) % DIVIDER;
        
    }
}