Problem of The Day: Unique Paths

Problem Statement

leetcode problem link

My Solution [Accepted]

public class Solution {
    private Dictionary<(int, int), int> Memo { get; set; } = new Dictionary<(int, int), int>();

    public int dp(int r, int c, int m, int n) {
        if (r > m || c > n) {
            return 0;
        }

        if (Memo.ContainsKey((r, c))) {
            return Memo[(r, c)];
        }

        if (r == m - 1 && c == n - 1) {
            return 1;
        }
        int right = dp(r + 1, c, m, n);
        int down = dp(r, c + 1, m, n);
        Memo[(r, c)] = right + down;
        return right + down;
    }

    public int UniquePaths(int m, int n) {
        return dp(0, 0, m, n);
    }
}

Editorial

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        if m == 1 or n == 1:
            return 1

        return self.uniquePaths(m - 1, n) + self.uniquePaths(m, n - 1)

Approach 1: Dynamic Programming

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

        for (int col = 1; col < m; ++col) {
            for (int row = 1; row < n; ++row) {
                d[col][row] = d[col - 1][row] + d[col][row - 1];
            }
        }

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

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        d = [[1] * n for _ in range(m)]

        for col in range(1, m):
            for row in range(1, n):
                d[col][row] = d[col - 1][row] + d[col][row - 1]

        return d[m - 1][n - 1]