(DP, Medium) Unique Paths

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

오른쪽과 아래로만 이동 가능하다는 제약이 있다.
그렇다면 i, j 에는 i-1과 j-1값을 더해주면 된다고 생각했다.

방어조건으로는 n이나 m이 1인 경우 무조건 1을 리턴하도록 했다 (한가지 수밖에 없음)

dp는 [m][n] 사이즈로 세팅해주고, 경우의 수 누적한다.
초기값은 오른쪽과 왼쪽 이동밖에 없으므로 [0][1]과 [1][0]에 1을 세팅한다.

이후 초기에 생각했던 아이디어대로 i-1, j-1값을 더해주면 되는데
이 과정에서 누락된 것이 있음

i또는 j가 0인 케이스도 고려를 해야 한다는 것 - 맨 위쪽이나 맨 왼쪽
이 경우에는 i-1 또는 j-1 둘 중 하나를 누적해야 한다.

시간복잡도는 O(n * m)이다.

class Solution {
    public int uniquePaths(int m, int n) {
        if (n + m <= 3) return 1;
        if (n == 1 || m == 1) return 1;

        int[][] dp = new int[m][n];
        dp[0][1] = 1;
        dp[1][0] = 1;

        for (int i=0; i<m; i++) {
            for (int j=0; j<n; j++) {

                if (i == 0 || j == 0) {
                    if (j != 0) {
                        dp[i][j] += dp[i][j - 1];
                    } else if (i != 0) {
                        dp[i][j] += dp[i - 1][j];
                    }
                } else {
                    dp[i][j] += dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }

        return dp[m - 1][n - 1];
    }
}

근데 코드가 드럽다.
i가 0이거나 j가 0인건 굳이 해당 반복문 안에서 논리 체크할 필요가 없다.
똑같은 논리로 [i][0] 과 [0][j] 값을 미리 밖에서 세팅해줄 수도 있다.

class Solution {
    public int uniquePaths(int m, int n) {
        if (n == 1 || m == 1) return 1;

        int[][] dp = new int[m][n];
        
        for (int i=0; i<m; i++) {
            dp[i][0] = 1;
        }

        for (int j=0; j<n; j++) {
            dp[0][j] = 1;
        }

        for (int i=1; i<m; i++) {
            for (int j=1; j<n; j++) {
                dp[i][j] += dp[i - 1][j] + dp[i][j - 1];
            }
        }

        return dp[m - 1][n - 1];
    }
}