سوال ACM

[Developer Programmer]

فرض کنید ماتریس n*n داریم
می خواهیم از درایه اول به درایه n بریم .
مسیری بیابید که جمع درایه های آن مسیر... در برابر سایر مسیرها ... کمترین باشد
:گیج:

[مهدی]

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


Unidirectional TSP Problem:

Input: An m*n matrix, each cell contains the cost of passing thru that cell.
Output: A path with minimum path-sum from column 0 (leftmost) to column n-1 (rightmost). The path can wraps horizontally.

Let M(i,j) be the minimum value of Unidirectional TSP problem for row i and column j and A[i,j] be the value of the matrix of size m*n. i and j starts from index 0.

Recurrence Relation:

;; For first column (col 0), the minimum value is the array value itself.
M[i][0] = A[i][0];

;; For all column j > 0, the minimum value is between one of these three,
;; plus the value of A[i][j].
M[i][j] = A[i][j] + Min(M[(i+m-1)%m][j-1],
M[i][j-1],
M[(i+1)%m)][j-1]);
;; To output the path, remember the previous row that we choose at current
;; column.


منبع Steven Halim Website