给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

    说明：每次只能向下或者向右移动一步。

    示例 1：
    image.png
    输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
    输出：7
    解释：因为路径 1→3→1→1→1 的总和最小。

    1. class Solution {
    3.     /**
    4.      * @param Integer[][] $grid
    5.      * @return Integer
    6.      */
    7.     function minPathSum($grid) {
    8.         $width = count($grid);
    9.         $height = count($grid[0]);
    10.         $dp = [];
    11.         $dp[0][0] = $grid[0][0];
    12.         for($i = 1; $i<$width;$i++ ){
    13.             $dp[$i][0] = $dp[$i-1][0] + $grid[$i][0];
    14.         }
    15.         for($i = 1; $i<$height;$i++ ){
    16.             $dp[0][$i] = $dp[0][$i-1] + $grid[0][$i];
    17.         }
    18.         for($i = 1;$i < $width;$i++){
    19.             for($j = 1;$j < $height;$j++){
    20.                 $dp[$i][$j] = min($dp[$i-1][$j],$dp[$i][$j-1]) + $grid[$i][$j];
    21.             }
    22.         }
    23.         return $dp[$width-1][$height-1];
    24.     }
    25. }

    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/minimum-path-sum
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。