Чтобы решить эту проблему, вам нужно помнить, что DP пытается имитировать c исчерпывающий поиск. В вашем примере, вор должен выбрать для каждого дома, если он должен грабить его или нет. У него есть дополнительное ограничение на количество последовательных домов, которые он «посетил» (об этом можно подумать как о базовом предложении, я считаю, что его проще придерживаться).
Это дает нам следующую рекурсивную формулу:
Base clause 1 for forbidden path:
T(i, 0) = -INFINITY
Base clause 2 before looting any house:
T(0, c) = 0
Recursive formula:
T(i, c) = max { T(i-1, c-1) + loot[i] , T(i-1, k) }
^ ^
loot i'th hourse Skip i'th house
Когда все готово, решение лежит с T(n,c) для некоторых 1 <= c <= k