64. 最小路径和

题意：

解题思路：

思路：
动态规划
状态：定义dp[i][j]表示到达[i, j]最小路径和
状态转移方程：dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[grid[i][$j];
初始化(第一行和第一列只有一条路可走)：
    dp[i][0] = dp[i - 1][0] + grid[i][0]; 
    dp[0][j] = dp[0][grid[i][0];
    dp[0][j]=dp[0][j - 1] + grid[0][grid[0][j - 1];

PHP代码实现：

class Solution {
    /**
     * @param Integer[][] $grid
     * @return Integer
     */
    function minPathSum($grid) {
        $depth = count($grid);
        $len = count($grid[0]);
        $dp = $grid;
        for ($i = 1; $i < $depth; $i++) $dp[$i][0] += $dp[$i-1][0];
        for ($i = 1; $i < $len; $i++) $dp[0][$i] += $dp[0][$i-1];
        for ($i = 1; $i < $depth; $i++) {
            for ($j = 1; $j < $len; $j++) {
                $dp[$i][$j] = min($dp[$i-1][$j], $dp[$i][$j-1]) + $grid[$i][$j];
            }
        }
        return $dp[$depth - 1][$len - 1];
    }
}

GO代码实现：

func minPathSum(grid [][]int) int {
    rows, cols := len(grid), len(grid[0])
    dp := make([][]int, rows)
    for i := 0; i < rows; i++ {
        dp[i] = make([]int, cols)
    }
    // 初始化
    dp[0][0] = grid[0][0]
    for i := 1; i < cols; i++ {
        dp[0][i] = dp[0][i-1] + grid[0][i]
    }
    for i := 1; i < rows; i++ {
        dp[i][0] = dp[i-1][0] + grid[i][0]
    }
    for i := 1; i < rows; i++ {
        for j := 1; j < cols; j++ {
            dp[i][j] = grid[i][j] + minInt(dp[i][j-1], dp[i-1][j])
        }
    }
    return dp[rows-1][cols-1]
}
func minInt(x, y int) int {
    if x <= y {
        return x
    }
    return y
}