Contents

# 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

 ``````1 2 `````` ``````Input: m = 7, n = 3 Output: 28 ``````

## example 2

 ``````1 2 3 4 5 6 7 `````` ``````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 :

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 `````` ``````func numTrees(n int) int { a:= make(map[int]int, 0) a = 1 a = 1 a = 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