На сетке находится робот m x n. Изначально робот находится в верхнем левом углу (т.е. grid[0][0]). Робот пытается переместиться в нижний правый угол (т.е. grid[m - 1][n - 1]). В любой момент времени робот может двигаться только вниз или вправо.
Учитывая два целых числа m и n, вернуть количество возможных уникальных путей, по которым робот может добраться до нижнего правого угла .
Тестовые случаи генерируются таким образом, чтобы ответ был меньше или равен .2 * 109
Пример 1:
Вход: m = 3, n = 7
Выход: 28
Пример 2:
Вход: m = 3, n = 2
Выход: 3
Пояснение: Из верхнего левого угла есть всего 3 способа добраться до нижнего правого угла:
1. Вправо -> Вниз -> Вниз
2. Вниз -> Вниз -> Вправо
3. Вниз -> Вправо -> Вниз
Ограничения:
- 1 <= m, n <= 100
пример решения на Go
func uniquePaths(m int, n int) int {
dp := make([][]int, m)
for i := range dp {
dp[i] = make([]int, n)
}
for i := 0; i < m; i++ {
dp[i][0] = 1
}
for j := 0; j < n; j++ {
dp[0][j] = 1
}
for i := 1; i < m; i++ {
for j := 1; j < n; j++ {
dp[i][j] = dp[i-1][j] + dp[i][j-1]
}
}
return dp[m-1][n-1]
}
Пояснение:
Создает 2D-срез (динамический размер) вместо массива
Инициализирует первую строку и первый столбец значением 1 (есть только один способ добраться до них — все вправо или все вниз)
Для каждой другой ячейки вычисляет количество путей как сумму путей из ячейки выше и ячейки слева
Возвращает значение в правом нижнем углу, которое содержит общее количество уникальных путей