1. 概述

给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。 说明：每次只能向下或者向右移动一步。
> 示例: 输入:

[

[1,3,1],

[1,5,1],

[4,2,1]

]

输出: 7

解释: 因为路径 1→3→1→1→1 的总和最小。

2. 解题

<?php
class Solution {
    public $way = [];
    /**
     * @param Integer[][] $grid
     * @return Integer
     */
    public function minPathSum($grid) {
        if (!$grid) {
            return 0;
        }
        $n = count($grid);
        $m = count($grid[0]);
        $this->dp($n, $m, $grid, [0, 0]);
        if (count($this->way) == 0) {
            return 0;
        }
        $min = array_sum($this->way[0]);;
        for ($i = 0; $i < count($this->way); $i++) {
            $min = min($min, array_sum($this->way[$i]));
        }
        return $min + $grid[0][0];
    }
    private function dp ($n, $m, $grid, $last, $way = []) {
        if ($last == [$n - 1, $m - 1]) {
            $this->way[] = $way;
            return;
        }
        if (isset($grid[$last[0]][$last[1] + 1])) {    // 右
            $way[] = $grid[$last[0]][$last[1] + 1];
            $this->dp($n, $m, $grid, [$last[0], $last[1] + 1], $way);
            array_pop($way);
        }
        if (isset($grid[$last[0] + 1][$last[1]])) {    // 下
            $way[] = $grid[$last[0] + 1][$last[1]];
            $this->dp($n, $m, $grid, [$last[0] + 1, $last[1]], $way);
            array_pop($way);
        }
    }
}
$grid = [
    [1,3,1],
    [1,5,1],
    [4,2,1]
];
$cls = new Solution();
$r = $cls->minPathSum($grid);
echo $r;
array_walk($cls->way, function (&$v){
    $v = implode(',', $v);
});
print_r($cls->way);