dp[x + 1] += dp[x]
dp[x] — сколько программ ведут из старта в x, то же, что K(x). Идём по числам слева направо и раздаём dp[x] туда, куда ведут стрелки из x.
Когда выбирать цикл. Путь очень длинный, например из 1 в 5000 командой +1. Рекурсия упрётся в предел вызовов, а цикл справится.
Запусти программу. Под ней - что она выводит.