[LeetCode- Ch8. 동적계획법] 1. 유일한 경로

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

Unique Paths - LeetCode

문제 조건

(0,0)부터 (n,m)까지 유일한 경로의 개수를 구한다.

 

문제 해결 순서

1. 한번에 이동가능한 경로를 이동경로 배열에 추가

2. 그 외의 경로 두 경로의 합으로 추가

---

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] arr = new int[n][m];
        for(int i=0;i<n;i++){
            arr[i][0]=1;
        }
        for(int j=0;j<m;j++){
            arr[0][j]=1;
        }
        for(int i=1;i<n;i++){
            for(int j=1;j<m;j++){
                if(arr[i][j]==0){
                    arr[i][j]=arr[i-1][j]+arr[i][j-1];
                }
            }
        }
        return arr[n-1][m-1];
    }
}