leetcode 62 java dp

문제

/*
m x n 격자(grid) 위에 로봇이 있습니다.
로봇은 처음에 좌측 상단 모서리(grid[0][0])에 위치해 있으며, 우측 하단 모서리(grid[m - 1][n - 1])로 이동하려고 합니다.
로봇은 한 번에 오른쪽 또는 아래쪽으로만 이동할 수 있습니다.

두 정수 m과 n이 주어졌을 때, 로봇이 우측 하단으로 이동할 수 있는 서로 다른 경로의 개수를 반환하세요.

테스트 케이스는 결과값이 2 * 10⁹ 이하가 되도록 생성됩니다.
*/

/*
dp[i][j] = dp[i-1][j] + dp[i][j-1];
*/

class Solution {
    public int uniquePaths(int m, int n) {
        int [][] dp = new int[m+1][n+1];
        for(int i=1; i<=m; i++) {
            dp[i][1] = 1;
        }
        for(int j=1; j<=n; j++) {
            dp[1][j] = 1;
        }

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

        return dp[m][n];
    }
}

 

 

일단 가장먼저 떠오른게 중학교때 저런걸 배웠다는거다 ..

좌측과 위쪽에 1을다 넣고 그숫자를 가지고 경우의 수를 계산하는 문제이다.

 

점화식은

dp[i][j] = dp[i-1][j] + di[i][j-1] 으로 나타낼 수 있다. 이말은 좌측에서 오는 경우와 우측에서 오는 경우를합치면

현재 내자신이 서있는 위치까지 오는 경우의 수를 계산할 수 있다,

 

어려운 문제는 아니다. 

시간복잡도는 o(mn)이다.