Статья Автор: Деникина Н.В., Деникин А.В.

Таблица в цикле

Таблица из первой тетради, но в цикле

Кроме рекурсии есть второй способ: заполнить таблицу циклом, автоматизировать то, что делали руками. Программа не боится очень длинных цепочек.


dp[x + 1] += dp[x]

dp[x] — сколько программ ведут из старта в x, то же, что K(x). Идём по числам слева направо и раздаём dp[x] туда, куда ведут стрелки из x.

Когда выбирать цикл. Путь очень длинный, например из 1 в 5000 командой +1. Рекурсия упрётся в предел вызовов, а цикл справится.

Запусти программу. Под ней - что она выводит.



Вывод программы:

8

Команды +1 и +2. В таблице dp[5] = 3 и dp[6] = 5. Чему станет равно dp[7]?


Что будет, если в цикле написать dp[x + 1] = dp[x] вместо dp[x + 1] += dp[x]?

Печать