Задача

Робот находится в левом верхнем углу сетки m x n (отмечен как ‘Start’ на диаграмме ниже).

Робот может двигаться только вниз или вправо в любой момент времени. Робот пытается достичь правого нижнего угла сетки (отмечен как ‘Finish’ на диаграмме ниже).

Сколько существует возможных уникальных путей?

Пример 1

Вход: m = 7, n = 3
Выход: 28

Пример 2

Вход: m = 3, n = 2
Выход: 3
Объяснение:
Из левого верхнего угла существует всего 3 способа достичь правого нижнего угла:
1. Вправо -> Вправо -> Вниз
2. Вправо -> Вниз -> Вправо
3. Вниз -> Вправо -> Вправо

Ограничения

• 1 <= m, n <= 100
• Гарантируется, что ответ будет меньше или равен 2 * 10 ^ 9.

Решение

Динамическое программирование

Основная идея - динамическое программирование:

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]
}