.
2019-11-20 吴亲库里 库里的深夜食堂
这道题和机器人的题目很像，都是从左上角方格走到方格的右下角，每次也都只能往下或者往右，但是不同点在于，机器人是求走法。而这道题求到达终点，最少花费的值。
思路还是可以用动态规划来解，也是从底部开始分析。那么每次 (i,j) 的情况分为四种，给定的是二维数组 $grid ,初始情况状态的定义 $dp[$i][$j]=$grid[$i][$j],这个是没有争议的，初始的状态当然就是右下角的最小值。那么其他情况，如果行还是最后一行，列不是最后一行的最后一列了，那么 状态转移方程呢？比如图2的位置 $dp[2][1] = $grid[2][1] + $dp[2][2]，这里的 $dp[2][2] 也就是初始的右下角的值1。我们再分析一种情况，比如图中5 的位置，因为从它往下走 只能是向下或者向右，现在我们是自底向上进行递推的，所以从底部到达这个点上的最小值只可能是
$dp[1][1] = $grid[1][1] + min($dp[2][1], $dp[1][2]) 这个首先到达5这个点最小值肯定得加上它自身吧所以 $grid[1][1] ,其实只能是它下面过来的 $dp[2][1],或者右边过来的 $dp[1][2]，哪条路线过来的状态小，就取哪条 min。
/**
* @param Integer[][] $grid
* @return Integer
*/
function minPathSum($grid)
{
$dp = [];
$m = count($grid);
$n = count($grid[0]);
for ($i = $m - 1; $i >= 0; $i--) {
for ($j = $n - 1; $j >= 0; $j--) {
if ($i == $m - 1 && $j != $n - 1) {
$dp[$i][$j] = $grid[$i][$j] + $dp[$i][$j + 1];
} else if ($j == $n - 1 && $i != $m - 1) {
$dp[$i][$j] = $grid[$i][$j] + $dp[$i + 1][$j];
} else if ($j != $n - 1 && $i != $m - 1) {
$dp[$i][$j] = $grid[$i][$j] + min($dp[$i + 1][$j], $dp[$i][$j + 1]);
} else {
$dp[$i][$j] = $grid[$i][$j];
}
}
}
return $dp[0][0];
}
