Nemie jasna zosto pominuva so greedy resenie a so DP(dinamicko programiranje) resenie ne pominuva.
Ova e resenieto za koe pominuva
a ova e resenieto kade sto pagja na runtime
Prasanjeto mi bese zosto zadacata e napravena samo da se resava so greedy approach a ne kako sto treba.
Ova go sogledav koga vidov deka vo zadacata pisuva da se najdi optimalnoto resenie kade sto ke ima minimalna razlika pomegju dvete grupi od nakiti no za dolniot slucaj ako odime po greedy resenieto(za koe pominuva 10/10) ke bide
14 12 10 20 22 ====> greedy (22 + 12 + 10 = 44 i 20 + 14 = 34 sto ke ispecati (34 44) no treba da bide (10 + 12 + 14 = 36 20 + 22 = 42 ) sto znaci pagja na ovoj slucaj no 10/10 pominuva na od MENDO slucaite sto ne mie jasno ....)
dodeka so DP resenieto si pecati najoptimalnoto grupiranje (36 42) no pagja na runtime za 4 slucai sto ne mie jasno zosto vaka e postavena zadacata.
Задачата е наменета да се реши со динамичко програмирање, само што твоето решение го надминува меморискиот лимит (пресметај ги димензиите на dp матрицата и лесно ќе се увериш во тоа).
За да се надмине овој проблем, клучно е да се увиди кои податоци не треба да ги чуваме. За да пресметаме произволен елемент од матрицата dp[i][j], нас ни требаат само вредностите од редот i-1, сите останати редици не ни играат улога, од што може да се заклучи дека во еден момент нам ни е потребно да чуваме само 2 редици од матрицата (претходната редица и таа што во сегашниот момент ја пресметуваме), што многу ни ја намалува меморијата.