Dinamiskās programmēšanas problēmas
Dinamiskā programmēšana jeb DP ir veids, kā risināt problēmas. Tas nav viens konkrēts algoritms. DP algoritmi pat savā starpā diezgan atšķiras, bet tiem ir dažas kopīgas iezīmes:
- Eksistē vairāki stāvokļi, kas var apzīmēt apakšproblēmu.
- Eksistē sākumstāvoklis, kuru par pamatu izmanto, lai risinātu apakšproblēmas.
- Katru apakšproblēmu risina balstoties uz kādu jau iepriekš atrisinātu apakšproblēmu vai apakšproblēmām.
Var redzēt, ka, atšķirībā no alkatīgajām metodēm, kuras risinot, apakšproblēma tika risināta, ņemot tajā mirklī šķietami labāko rezultātu, DP balstās uz jau iepriekš izrēķinātiem rezultātiem. Piemēram, Fibonači rinda tiek risināta ar DP palīdzību, jo katrs elements nevis tiek saskaitīts no sākuma, bet tiek izveidots no iepriekš izrēķinātajiem rezultātiem.
Dinamiskās programmēšanas pieejas ir aptveramas, bet tās var slēpties zem daudzām un dažādām problēmām. Ja grafu teoriju var iemācīties un kādu daļu saskatīt bez pieredzes, tad DP problēmas pārsvarā var tikai ietrenēt un spēju tās saskatīt var attīstīt ar daudzu uzdevumu atrisināšanas palīdzību. Zemāk ir pievienotas saites ar informāciju par dažādiem DP paveidiem un TopCoder foruma raksts par uzdevumiem, kuru risinājumi ir DP.
