How Can I solve this -( Unidirectional TSP ) problem !
Problem : Given an m x n matrix of integers, you are to write a program that computes a path of minimal weight. A path starts anywhere in column 1 (the first column) and consists of a sequence of steps terminating in column n (the last column). A step consists of traveling from column i to column i+1 in an adjacent (horizontal or diagonal) row. The first and last rows (rows 1 and m) of a matrix are considered adjacent, i.e., the matrix “wraps” so that it represents a horizontal cylinder. The weight of a path is the sum of the integers in each of the n cells of the matrix that are visited.
Will be grateful if anyone can help. Thank You.
Define your states dp[row][col] which is the minimal weight path starting at cell (row, col)
Now transitioning should be easy:
You just take the minimum of all 3
The base case is that dp[i][m-1] = a[i][m-1] for all i
thank you so much.