Ezért kellett volna a teljes indukcióról tanulni a középiskolában, vagy még az általánosban.
Mikor érdemes az utca utolsó házát kirabolni? Ha az utolsó előtti nélkül, meg a mostanival többet szedek össze, mint ha ezt kihagyom és az utolsó előttiig rabolok. f(n)=max(x_n+f(n-2), f(n-1))
A dinamikus programozás arról szól, hogy a rekurziót - amit az előbbi meggondolás tartalmaz - átírjuk ciklusra, és ehhez nyilvántartjuk, hogy az 1...k házszámú házakból mennyi zsákmányolható. Ezt - az összeget - tartalmazná a dp[k] elem.
Általános iskolai versenyeken az utca hossza rendszerint már akkora, hogy a rekurzió már lassú néhány tesztesetnél (exponenciális bonyolultság), míg a dinamikus programozás (lineáris bonyolultság) nevetve megold mindent.