U polja kvadratne matrice dimenzija NxN upisani su pozitivni brojeve. Potrebno je pronaći najveću moguću sumu N brojeva iz ove matrice takvih da nikoja dva ne pripadaju ni istom redu ni istoj koloni.
Za matricu:
1 2 (3)
(3) 2 1
1 (3) 2
najveća suma je 9.
Na prvi pogled mi se učinilo kao jednostavan dp, ali nakon više pokušaja nisam pronašao optimalnije rješenje.