Problem

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).

How many possible unique paths are there?

example 1

Input: m = 7, n = 3
Output: 28

example 2

Input: m = 3, n = 2
Output: 3
Explanation:
From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Right -> Down
2. Right -> Down -> Right
3. Down -> Right -> Right

Constraint

• 1 <= m, n <= 100
• It’s guaranteed that the answer will be less than or equal to 2 * 10 ^ 9.

Solution

Dynamic programming

Main idea - dynamic programming :

func numTrees(n int) int {
    a:= make(map[int]int, 0)
    a[0] = 1
    a[1] = 1
    a[2] = 2
    return helper(n , a)
}

func helper(n int, a map[int]int) int {
    if _, ok := a[n]; ok {
        return a[n]
    }
    res := 0
    for idx := 0; idx<n; idx++ {
        res += (helper(idx, a)*helper(n-idx-1, a))
    }

    a[n] = res

    return a[n]  
}