Programowanie dynamiczne

0

Jak rozwiązać takie zadanie:
zadanie_algo.jpg

Z tego co wiem podczas programowania dynamicznego powinno się zapisywać wszystkie wyniki np. w tablicy, ale nie wiem jak to powinno wyglądać w pseudokodzie, i jak obliczyć złożoność algorytmiczną ?

Pseudokod który napisałem bez użycia tablicy wygląda następująco :

F(n,k)

if k=0
  return 1
if n=0 i k>0
  return 2*k
else 
  return F(n,k-1)+F(n-1,k)

Jak należy go zmienić aby był wykonany za pomocą metody programowania dynamicznego ?

1

Należy pomyśleć. Zrób sobie tablicę gdzie będziesz przechowywał wartości f(x,y) i licz tą tablicę od początku. Następnie w pętli zamiast liczyć na pałę wszystkie współczynniki potrzebne do wyliczenia f(k,n) zrobisz po prostu
tablica[n,k-1]+tablica[n-1,k]

0
F(n,k)
 
if k=0
  return T[n,k]<-1
if n=0 i k>0
  return T[n,k]<-(2*k)
else 
  return T[n,k-1]+T[n-1,k]

W ten sposób ?

0

Tak. W ten właśnie sposób :)

0

Ok, dzięki za pomoc :) A jak obliczyć teraz złożoność takiego algorytmu?

2

Bardzo prosto. Policz ile operacji musisz wykonać żeby wyliczyć f(n,k). Łatwo zauważyć że aby wyliczyć f(n,k) wystarczy ci jedno przejście przez tablicę, więc złożoność to O(n*k)

1 użytkowników online, w tym zalogowanych: 0, gości: 1