h2. Reducerea loop-ului interior

În problemele de programare dinamică de multe ori prima complexitate obţinută nu este optimă. Mai exact, recurenţa obţinută iniţial poate fi îmbunătăţită sau calculată mai rapid. De multe ori, pentru aceasta se optimizeaza loop-ul interior din calculul recurenţei. Acest lucru se poate face bazat fie pe observaţii specifice problemei, fie pe tehnici mai clasice.
 

Să considerăm următoarea problema:
h3(#problema-1). Problema 1: 'Drilling':http://www.main.edu.pl/user.phtml?op=showtask&task=wie&con=PA2009&lang=en (Algorithmic Engagements 2009, Round 3)