سوال ACM

این یه برنامه داینامیک به حساب میاد و خیلی هم مساله معروفیه! البته خود همین مساله نه اما مشابهش.

Unidirectional TSP Problem&#58;



Input&#58; An m*n matrix, each cell contains the cost of passing thru that cell.

Output&#58; A path with minimum path-sum from column 0 &#40;leftmost&#41; to column n-1 &#40;rightmost&#41;. The path can wraps horizontally.



Let M&#40;i,j&#41; be the minimum value of Unidirectional TSP problem for row i and column j and A&#91;i,j&#93; be the value of the matrix of size m*n. i and j starts from index 0.



Recurrence Relation&#58;



;; For first column &#40;col 0&#41;, the minimum value is the array value itself.

M&#91;i&#93;&#91;0&#93; = A&#91;i&#93;&#91;0&#93;;



;; For all column j > 0, the minimum value is between one of these three,

;; plus the value of A&#91;i&#93;&#91;j&#93;.

M&#91;i&#93;&#91;j&#93; = A&#91;i&#93;&#91;j&#93; + Min&#40;M&#91;&#40;i+m-1&#41;%m&#93;&#91;j-1&#93;,

                        M&#91;i&#93;&#91;j-1&#93;,

                        M&#91;&#40;i+1&#41;%m&#41;&#93;&#91;j-1&#93;&#41;;

;; To output the path, remember the previous row that we choose at current

;; column.

منبع Steven Halim Website