Код Senior Динамическое программирование обновлено
Число путей в сетке
Условие
Сколько путей из левого верхнего угла в правый нижний, если ходить можно только вправо и вниз?
Примеры
uniquePaths(3, 7) // 28
uniquePaths(3, 2) // 3
uniquePaths(1, 1) // 1
Как подойти
dp[r][c] = dp[r−1][c] + dp[r][c−1], свёрнутое до одной строки: row[c] += row[c−1] переиспользует старое значение как «сверху», а новое соседнее как «слева». Комбинаторная формула C(m+n−2, m−1) тоже верна - назови обе.
Подсказки: 2
- В каждую клетку приходят только сверху и слева.
- Достаточно одной строки таблицы.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.
Предыдущий вопрос
Максимальная сумма подмассива
Следующий вопрос
Расстояние Левенштейна между двумя словами