꿀잠

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

2차원 DP 문제이다. 로봇은 좌상단에서 시작해 우측, 또는 아래로만 이동할 수 있으므로 첫 행, 첫 열은 가는 방법이 한 가지로 고정이다. 해당 조건에서 안쪽 좌표들의 경우 좌측에서 오는 경우와 위에서 오는 경우 두 가지 경우의 합이 해당 좌표로 가는 방법이기에 해당 조건으로 점화식을 세워 문제를 해결할 수 있었다.

public class Solution {  
    public int uniquePaths(int m, int n) {  
        int[][] dp = new int[m][n];  
  
        for(int i = 0; i < m; i++){  
            dp[i][0] = 1;  
        }  
  
        for(int i = 0; i < n; i++){  
            dp[0][i] = 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];  
    }  
}