Get the smallest amount of matrix element combination

Question

Yesterday, one of my friends had a problem asking him to find a solution.

Problem

I have matrix(nxm) . I need to find out the smallest amount I can produce from this matrix element.

Condition:

• Counting should begin only with the upper left cell. AND
• Should end in the bottom right cell.
• The algorithm should consider all possible paths.
• So I need to find the smallest possible amount.

After several hours of work, I can find a sample for this. But I do not know how to implement it in code.

Here is my template:

How to implement this?

Edit:

 $Cost = array(); for ($x = 0; $x < $rows; $x++) { $Cost[0][$x] = $matrix[0][$x]; for ($y = 1; $y < $cols; $y++) { $Cost[$y][0] = $matrix[$y][0]; } } for ($x = 1; $x < $rows; $x++) { for ($y = 1; $y < $cols; $y++) { $Cost[$x][$y] = intval($matrix[$x][$y]) + min(intval($Cost[$x - 1][$y]), intval($Cost[$x][$y - 1])); } } 

The matrix array I'm trying is:

 array(2) { [0]=> array(3) { [0]=> string(1) "3" [1]=> string(2) "44" [2]=> string(2) "75" } [1]=> array(3) { [0]=> string(2) "21" [1]=> string(2) "98" [2]=> string(2) "60" } } 

Result:

 array(3) { [0]=> array(2) { [0]=> string(1) "3" [1]=> string(2) "44" } [1]=> array(3) { [0]=> string(2) "21" [1]=> int(119) [2]=> int(0) } [2]=> array(1) { [0]=> NULL } } 

Answer 1

It seems that you can only go right and down. For this case (otherwise, use path search algorithms), note that you can enter each cell either from the top cell or from the left cell. The cheapest path to this cell will be the minimum of these values. Therefore, the DP solution may look like (pseudo-code):

see corrections here

 Cost[0, 0] = matrix[0, 0] for x = 1 to cols - 1 Cost[0, x] = matrix[0, x] + Cost[0, x-1] //0th row for y = 1 to rows - 1 Cost[y, 0] = matrix[y, 0] + Cost[y-1, 0] //0th column //proper filling of 0th row and 0th column for y = 1 to rows - 1 for x = 1 to cols - 1 Cost[y, x] = matrix[y, x] + Min(Cost[y-1, x], Cost[y, x-1]) 

then the cost of [n-1, n-1] is what you need

Answer 2

Update to MBo . Considering that n * m (n = 3, m = 4 in your message) The consumed space can be reduced to O (N) only by remembering the result for the previous row (column).

 Cost[0] = matrix[0, 0] for x = 1 to m - 1 Cost[x] = matrix[0, x] + Cost[x-1] for y = 1 to n - 1 Cost[0] += matrix[y, 0] for x = 1 to m - 1 Cost[x] = matrix[y, x] + Min(Cost[x-1], Cost[x]) output(Cost[n-1]) 

I don't know how to write in PHP ... Here is an example python code

 matrix = [ [3, 44, 75], [21, 98, 60], ] n = len(matrix) m = len(matrix[0]) cost = [0] * m cost[0] = matrix[0][0] for x in xrange(1, m): cost[x] = matrix[0][x] + cost[x-1] for y in xrange(1, n): cost[0] += matrix[y][0] for x in xrange(1, m): cost[x] = matrix[y][x] + min(cost[x-1], cost[x]) print cost[-1]