Почему это работает
- Из клетки самый дешёвый путь вниз — её число плюс меньший из самых дешёвых путей из двух клеток под ней. Если идти по строкам снизу, эти две всегда уже готовы.
- Каждая клетка нижней строки — уже законченный путь, поэтому в копии треугольника там сразу верные значения, и других базовых случаев не нужно.
- Выбирать на спуске клетку подешевле — значит смотреть только на строку вперёд: здесь так берут 1 и платят 17. Каждая клетка best уже учла все пути под собой.
Сложность
Время O(n²) для n строк: каждая из примерно n²/2 клеток — один min и одно сложение. Память O(n²) на копию; строка читает только строку под собой, так что хватит одного массива из n чисел.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗