Müasir cəmiyyətdə informasiyanın həcmi planetin 20 IL əvvəl mövcud olan bütün informasiya həcmini üstələyir. Bütün daxil olan məlumatların emalı çox vaxt aparır

Üst-üstə düşən alt tapşırıqlar:

DP məsələsində üst-üstə düşən alt tapşırıqlar olmalıdır. Bu o deməkdir ki, eyni funksiyanın bir neçə dəfə hesablandığı bəzi ümumi hissə olmalıdır. Məsələn: F(5) və F(6) məsələsinin hər ikisi F(4) və F(3) kimi alt məsələlərə malikdir. Məhz bu səbəbdən hesablanan qiymətləri massivimizdə saxlamışıq.

• 
  Optimal struktur:
  

Tutaq ki, sizdən g(x) funksiyasını minimuma endirmək tələb olunur. Bilirsiniz ki, g(x)-in qiyməti g(y) və g(z)-dən asılıdır. İndi g(y) və g(z) hər ikisini minimuma endirməklə g(x)-ni minimuma endirə bilsək, yalnız bu halda problemin optimal alt quruluşa malik olduğunu deyə bilərik. Əgər g(x) g(y)-i minimuma endirməklə minimuma endirilirsə və g(z)-ni minimuma endirmək və ya maksimuma çatdırmaq g(z)-ə təsir etmirsə, onda bu məsələnin optimal alt strukturu yoxdur. Sadə dillə desək, əgər problemin optimal həlli onun alt probleminin optimal həllindən tapıla bilərsə, o zaman problemin optimal alt quruluş xassəsinə malik olduğunu deyə bilərik.
Nəticələr cədvəldə və qrafikdə təqdim olunur [39].

Cədvəl. Fibonaççi ədədinin hesablanması nəticələrinin cədvəli.

Fibonaççi ədədi		40	42	43	44	45
Yerinə yetirilmə vaxtı, ms	Rekursiv metod	11929	26963	41552	66825	104383
	Dinamik proqramlaşdırma	1125	1174	1282	1350	1406

Şəkil . Fibonaççi ədədinin hesablanması nəticələrinin qrafiki.

Yuxarıda təqdim olunan nəticələrdən aydın görünür ki, dinamik proqramlaşdırmadan istifadə edərək hesablama vaxtı rekursiya ilə hesablama vaxtı ilə müqayisədə xeyli aşağıdır. Fərq xüsusilə 40-cı və daha böyük Fibonaççi ədədi hesablanarkən nəzərə çarpır.

Dinamik proqramlaşdırmada vəziyyəti başa düşmək üçün bir nümunəyə baxaq. N elementdən r elementi neçə üsulla seçə bilərik? Bu ⁿC_r(n,r) kimi göstərilir. İndi bir element götürək.

• 
  Əgər siz element seçməsəniz, ondan sonra ilə verilən qalan n-1 elementlərindən r element götürməlisiniz.
  
• 
  Əgər siz element seçmisinizsə, ondan sonra ilə verilən qalan n-1 elementlərindən r-1 element götürməlisiniz.
  

Bu ikisinin cəmi bizə üsulların ümumi sayını verir, yəni:

Əgər ⁿC_r(n,r) –i n və r-i parametr kimi qəbul edən funksiya saysaq və ⁿC_r - i funksiyanın qiyməti kimi qəbul etsək, onda yuxarıda dediyimiz münasibəti bu cür yaza bilərik:
ⁿC_r(n,r) = ⁿC_r(n-1,r) + ⁿC_r(n-1,r-1)
Bu, rekursiv münasibətdir. Onu başa çatdırmaq üçün baza registrlərini təyin etməliyik. Bilirik ki, ⁿC_r(n,r)=n, həmçinin ⁿC_n(n,r)=1 . Bu iki bərabərliyi əsas başlanğıc kimi qəbul edərək, ⁿC_r -i hesablayan alqoritmi bu şəkildə qura bilərik:
Procedure nCr(n, r):
if r is equal to 1
Return n
else if n is equal to r
Return 1
end if
Return nCr(n-1,r) + nCr(n-1,r-1)
Proseduru qrafik şəkildə nəzərdən keçirsək, bəzi rekursiyaların bir dəfədən çox çağırıldığını görə bilərik. Məsələn: n = 8 və r = 5 götürsək, alırıq:

Biz dp massivindən istifadə edərək təkrar çağırışdan qaça bilərik. 2 parametr olduğu üçün bizə 2D massivi lazım olacaq. Biz dp massivinin bütün elementlərinə -1 mənimsədirik, burada -1 qiymətin hələ hesablanmadığını bildirir. Prosedurumuz belə olacaq: