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.