Note de curs, clasele 9-10, 13 martie 2014

From Algopedia
Jump to navigationJump to search

Discutarea temei

Problema Die Hard:

  • Algoritmul în O(n3): pentru fiecare punct (i, j) din matrice, trebuie să fi ajuns în el de la un punct (k, j - 1), mergând un pas către est, apoi de la linia k la linia i' către nord sau sud, după caz. Dorim să calculăm distanța minimă până în fiecare din cele O(n2) puncte, iar fiecare punct se calculează în O(n).
  • Reducerea la O(n2)

Programare dinamică (probleme)

Vom urma în continuare notele de la clasele 11-12.