获得矩阵元素组合的最小和

Question

昨天我的一个朋友遇到了一个问题,请我找到解决方案.

问题

我有一个matrix(n x m).我需要找出从这些矩阵元素中可以产生的最小和.

条件是:

• 计数应该只从左上角的单元格开始.和
• 应该在右下角的单元格结束.
• 算法应计算所有可能的路径
• 通过这种方式,我需要找到可能的最小总和.

经过几个小时的挣扎,我能找到一个模式.但我不知道如何在代码中实现它.

这是我的模式:

我该如何实现呢？

编辑:

$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]));
    }
}

矩阵阵列我正在尝试:

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" } }

结果:

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

看来你只能向右和向下走.对于这种情况(否则使用路径查找算法)请注意,您可以从上部单元格或左侧单元格进入每个单元格.从这些值开始,这个单元格最便宜的路径将是最小的.所以DP解决方案可能看起来像(伪代码):

看这里的更正

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]) 

那么成本[n-1,n-1]就是你所需要的