Skip to main content

62. Unique Paths

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

Python​

Top Down DP - Right to Left​

from functools import cache


class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        @cache
        def dp(row, col):
            if row == 1 or col == 1:
                return 1
            return dp(row-1, col) + dp(row, col-1)

        return dp(m, n)

Top Down DP - Left to Right​

from functools import cache


class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        @cache
        def dp(row, col):
            if row == m-1 or col == n-1:
                return 1
            return dp(row+1, col) + dp(row, col+1)

        return dp(0, 0)

Go​

Top Down DP​

func uniquePaths(m int, n int) int {
    cache := make(map[string]int)
    return dp(m-1, n-1, cache)
}

func dp(row int, col int, cache map[string]int) int {
    if (row == 0 || col == 0) {
        return 1
    }
    key := fmt.Sprintf("%d:%d", row, col)

    if val, isCached := cache[key]; isCached {
        return val
    }

    cache[key] = dp(row-1, col, cache) + dp(row, col-1, cache)

    return cache[key]
}