Почему это работает
- Любой путь в (r, c) делает последний шаг либо вниз из (r - 1, c), либо вправо из (r, c - 1). Обоими сразу не кончается ни один путь, поэтому пути в клетку — это ровно пути в эти две клетки, сложенные вместе.
- В клетку верхней строки или левого столбца ведёт только прямая линия от старта, поэтому в ней 1. С этих клеток таблица и начинается.
- По строкам слева направо обе клетки, которые читает клетка, заполнены раньше неё, поэтому каждая клетка считается один раз из готовых чисел.
Сложность
Время O(m × n): каждая клетка — одно сложение. Память O(m × n) на таблицу; клетка читает только свою строку и строку над ней, так что хватит одной строки из n клеток.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗