64.md

:pencil2:基础刷题之(64. Minimum Path Sum)

. 2019-11-20 吴亲库里 库里的深夜食堂

:pencil2:描述

这道题和机器人的题目很像，都是从左上角方格走到方格的右下角，每次也都只能往下或者往右，但是不同点在于，机器人是求走法。而这道题求到达终点，最少花费的值。

:pencil2:题目实例

​

---

:pencil2:题目分析

思路还是可以用动态规划来解，也是从底部开始分析。那么每次 (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。

:pencil2:最终实现代码

/**
     * @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];
    }

---

联系

​