LeetCode 62번
https://leetcode.com/problems/unique-paths/description/

문제

---

생각하기

---

• DP, memoization 문제이다.

• 오른쪽 방향과, 아래 방향으로만 이동 가능하다는 조건을 고려해서 문제를 풀면 된다.

동작

결과

코드

---

import java.util.*;

class Solution {
    private static int N, M;
    private static int[][] memo;
    private static final int[] dirX = {1, 0};
    private static final int[] dirY = {0, 1};

    public int uniquePaths(int m, int n) {
        // 0, 0에서 출발해서 m - 1, n - 1로 도달 할 수 있어야한다.
        N = n;
        M = m;
        int ans = 0;

        memo = new int[N + 1][M + 1];        
        for(int i=0; i<=N; i++) {
            Arrays.fill(memo[i], -1);
        }

        return topDown(N - 1, M - 1);
    } // End of uniquePaths()

    private int topDown(int n, int m) {
        if(n == 0 && m == 0) {
            return 1;
        }

        if(n < 0 || m < 0) return 0;

        if(memo[n][m] != -1) return memo[n][m];

        memo[n][m] = 0;
        memo[n][m] = topDown(n - 1, m) + topDown(n, m - 1);

        return memo[n][m];
    } // End of topDown()
} // End of Solution class