Dynamic Programming
Given a m * n matrix, your task is to compute a path
from any element on the 1 st column to any element on the last column
at minimal cost. The path consists of several steps, each step is
moving from column j to column j+1 in an
adjacent (horizontal or diagonal) row. The first row and the last row
are considered as adjacent rows. The cost of a path is the sum of visited
integers.
The two slightly different matrices are shown in figure below. The minimum cost path is illustrated in the figure and the 2 nd path takes advantage of the adjacency property of the first and last row.
You'll be given two integers m and n that
indicate the number of rows and columns at the first line. The next m
lines will be the matrix and each line represents one row of the given
matrix. You're required to output the minimum cost.
Notes: : The test cases have the properties: number of rows is between 1 and 10; number of columns is between 1 and 100; number in matrix can be positive or negative; All path weights can be represented by 30-bit signed integer.
Example 1
Input:
5 6
3 4 1 2 8 6
6 1 8 2 7 4
5 9 3 9 9 5
8 4 1 3 2 6
3 7 2 8 6 4
Output:
16
Explanation:
the path: 1 2 3 4 4 5
Example 2
Input:
5 6
3 4 1 2 8 6
6 1 8 2 7 4
5 9 3 9 9 5
8 4 1 3 2 6
3 7 2 1 2 3
Output:
11
Explanation:
the path: 1 2 1 5 4 5