Dinamikang pagpoprograma

Paghahanap ng pinakamaikling landas sa isang grap gamit ang pinakamainam na substruktura; ang isang tuwid na linya ay nagpapahiwatig ng isang gilid; ang kulot na linya ay nagpapahiwatig ng pinakamaikling landas sa pagitan ng dalawang vertices na pinag-uugnay nito (bukod sa iba pang mga landas, hindi ipinapakita, nagbabahagi ng parehong dalawang vertices); ang naka-bold na linya ay ang pangkalahatang pinakamaikling landas mula simula hanggang layunin.

Ang dinamikang pagpoprograma (Ingles: dynamic programming) ay parehong paraan ng optimisasyong matematikal at paradigma ng algoritmo. Ang pamamaraan ay binuo ni Richard Bellman noong 1950s at nakahanap ng mga aplikasyon sa maraming larangan, mula sa inhinyeriyang pang-aeroespasyo hanggang sa ekonomiya.

Sa parehong konteksto ito ay tumutukoy sa pagpapasimple ng isang kumplikadong problema sa pamamagitan ng paghahati-hati nito sa mas simpleng mga sub-problema sa isang rekursibong paraan. Bagama't ang ilang mga problema sa pagpapasya ay hindi maaaring paghiwalayin sa ganitong paraan, ang mga pagpapasya na sumasaklaw sa ilang mga punto sa oras ay madalas na nahahati nang paulit-ulit. Gayundin, sa agham pang-kompyuter, kung ang isang problema ay malulutas nang husto sa pamamagitan ng paghahati-hati nito sa mga sub-problema at pagkatapos ay paulit-ulit na paghahanap ng pinakamainam na solusyon sa mga sub-problema, kung gayon ito ay sinasabing may pinakamainam na substruktura.

Kung ang mga sub-problema ay maaaring nailagay nang paulit-ulit sa loob ng mas malalaking problema, upang ang mga dinamikong pamamaraan ng pagpoprograma ay naaangkop, kung gayon ay mayroong kaugnayan sa pagitan ng halaga ng mas malaking problema at ng mga halaga ng mga sub-problema. Sa panitikang optimisasyon ang relasyong ito ay tinatawag na ekwasyong Bellman.