PROGRAMMING:Minimum path sum of matrices
Given a matrix, starting from the upper left corner, you can only go right or down each time, and finally reach the lower right corner. All the numbers on the path add up to the path sum, and return the smallest path sum of all the paths.
###Input format:
The first line is two numbers m and n (1 ≤ m, n ≤ 1000), which respectively represent the number of rows and columns of the matrix.
Next, there are m lines, n numbers in each line, separated by a space. The value of each number is a non negative integer that does not exceed 200.
###Output format:
Output the smallest path sum of all paths from the upper left corner to the lower right corner in one line.
###Input example:
```in
4 4
1 3 5 9
8 1 3 4
5 0 6 1
8 8 4 0
```
###Output example:
```out
twelve
```
###Example explanation:
Path 1, 3, 1, 0, 6, 1, 0 is the smallest sum of all paths, so 12 is returned.
answer：If there is no answer, please comment
Classical dynamic programming algorithm.
Suppose the size of matrix is m × N. The number of rows is m and the number of columns is n. A matrix DP [M] [n] with the same size as the matrix is formed. The value of DP [i] [J] represents the minimum path sum from the upper left corner (i.e. (0,0)) to (I, J). For all positions in the first row of the matrix, that is, (0, J) (0 ≤ J < n), the path from (0,0) to (0, J) can only go to the right, so the sum of paths from (0,0) to (0, J) is the cumulative result of M [0] [0.. J]. Similarly, for all positions in the first column of matrix, that is, (I, 0) (0 ≤ I < m), the path from (0,0) to (I, 0) can only go down, so the sum of paths from (0,0) to (I, 0) is the sum of these values of M [0.. I] [0].
For the example in the title, the values of the first row and the first column of DP are as follows:
In addition to other positions (I, J) in the first row and column, there are left positions (i-1, J) and upper positions (I, J-1). The path from (0,0) to (I, J) must pass through position (i-1, J) or position (I, J-1)
dp[i][j] = min{dp[i-1][j], dp[i][j-1]} + matrix[i][j]
The meaning is to compare the minimum path from (0,0) position to (I, J) position and the minimum path from (I, J-1) position to (I, J) position, which path is smaller. So the smaller path sum is the value of DP [i] [J]. For example, the final DP matrix is as follows:
Except for the first row and the first column, each location considers whether the path from the left to its own is smaller or the path from the top to its own is smaller. The bottom right corner is the answer to the whole question.
###Input format:
The first line is two numbers m and n (1 ≤ m, n ≤ 1000), which respectively represent the number of rows and columns of the matrix.
Next, there are m lines, n numbers in each line, separated by a space. The value of each number is a non negative integer that does not exceed 200.
###Output format:
Output the smallest path sum of all paths from the upper left corner to the lower right corner in one line.
###Input example:
```in
4 4
1 3 5 9
8 1 3 4
5 0 6 1
8 8 4 0
```
###Output example:
```out
twelve
```
###Example explanation:
Path 1, 3, 1, 0, 6, 1, 0 is the smallest sum of all paths, so 12 is returned.
answer：If there is no answer, please comment
Classical dynamic programming algorithm.
Suppose the size of matrix is m × N. The number of rows is m and the number of columns is n. A matrix DP [M] [n] with the same size as the matrix is formed. The value of DP [i] [J] represents the minimum path sum from the upper left corner (i.e. (0,0)) to (I, J). For all positions in the first row of the matrix, that is, (0, J) (0 ≤ J < n), the path from (0,0) to (0, J) can only go to the right, so the sum of paths from (0,0) to (0, J) is the cumulative result of M [0] [0.. J]. Similarly, for all positions in the first column of matrix, that is, (I, 0) (0 ≤ I < m), the path from (0,0) to (I, 0) can only go down, so the sum of paths from (0,0) to (I, 0) is the sum of these values of M [0.. I] [0].
For the example in the title, the values of the first row and the first column of DP are as follows:
In addition to other positions (I, J) in the first row and column, there are left positions (i-1, J) and upper positions (I, J-1). The path from (0,0) to (I, J) must pass through position (i-1, J) or position (I, J-1)
dp[i][j] = min{dp[i-1][j], dp[i][j-1]} + matrix[i][j]
The meaning is to compare the minimum path from (0,0) position to (I, J) position and the minimum path from (I, J-1) position to (I, J) position, which path is smaller. So the smaller path sum is the value of DP [i] [J]. For example, the final DP matrix is as follows:
Except for the first row and the first column, each location considers whether the path from the left to its own is smaller or the path from the top to its own is smaller. The bottom right corner is the answer to the whole question.