<Medium> Unique Paths (LeetCode : C#)

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

📕 문제 설명

로봇이 좌측 상단에서 출발해 우측 하단으로 움직인다. 로봇은 오른쪽 또는 밑으로만 움직일 수 있다. 로봇이 우측 하단에 도달할 수 있는 unique한 path 개수 반환하기

• Input
  행 개수 m, 열 개수 n
• Output
  로봇이 우측 하단으로 도달하는 unique한 path 개수

예제

풀이

수학에서 최단 거리 경우의 수 구하는 방식을 점화식으로 세워서 풀었다.

public class Solution {
    public int UniquePaths(int m, int n) {

        int[,] dp = new int[m, n];
        // 초기값 할당
        for (int i = 0; i < n; i++)
        {
            dp[0, i] = 1;
        }

        for (int i = 0; i < m; i++)
        {
            dp[i, 0] = 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];
    }
}

결과