( AszaltSzilva | 2021. 12. 01., sze – 16:54 )

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.