[LeetCode] 62. Unique Paths - 동적계획법(DP, Dynamic Programming) JAVA

https://leetcode.com/problems/unique-paths/description/

코드설명

동적계획법(DP, Dynamic Programming) 을 활용합니다.

 

기저사례로 먼저

DP 테이블의 최상단 Row와 최좌측 Col들을 모두 1개의 방법으로 밖에 도달하지 못한다는 의미로 1로 초기화시킵니다.

DP[i][j]가 의미하는 바는, (1, 1) 에서 (i, j)까지 갈 수 있는 경로를 의미합니다.

점화식을 세우면

DP[r][[c] = DP[r-1][ + DP[r][c-1] 입니다. (조건은 r == 1일떄와 c == 1 일때는 1입니다. )

코드

정답코드1입니다.

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] DP = new int[m + 1][n + 1];
        Arrays.fill(DP[1], 1);
        for(int r=1; r<=m; r++){
            DP[r][1] = 1;
        }
        for(int r=1; r<=m; r++){
            for(int c=1; c<=n; c++){
                DP[r][c] = DP[r-1][c] + DP[r][c-1];
            }
        }
        return DP[m][n];
    }
}

정답코드2입니다.

class Solution {
    int[][] cache;
    public int uniquePaths(int m, int n) {
        cache = new int[102][102];
        for(int[] c : cache){
            Arrays.fill(c, -1);
        }
        return DFS(m, n, 1, 1);
    }

    int DFS(int m, int n, int r, int c){
        if(r == m && c == n){
            return 1;
        }
        if(cache[r][c] != -1) return cache[r][c];

        int ret = 0;
        for(int[] dir : new int[][] {{1, 0}, {0, 1}}){
            int nr = r + dir[0];
            int nc = c + dir[1];
            if(nr > m || nc > n) continue;
            ret += DFS(m, n, nr, nc);
        }
        return cache[r][c] = ret;
    }
}