最小路径和

/*
 * 思路：
 * 1. 使用动态规划和Java Stream解决问题。
 * 2. 创建一个dp二维数组，其中dp[i][j]表示到达位置(i, j)的最小路径和。
 * 3. 初始化dp数组的第一个元素dp[0][0]为grid[0][0]。
 * 4. 填充dp数组的第一行和第一列。
 * 5. 使用嵌套循环填充剩余的dp数组，每个元素取决于其上方和左方元素的最小值加上当前grid的值。
 * 6. 返回dp数组的最后一个元素即为所求。
 */
import java.util.Arrays;
import java.util.stream.IntStream;

public class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m][n];
        dp[0][0] = grid[0][0];
        IntStream.range(1, m).forEach(i -> dp[i][0] = dp[i - 1][0] + grid[i][0]);
        IntStream.range(1, n).forEach(j -> dp[0][j] = dp[0][j - 1] + grid[0][j]);
        IntStream.range(1, m).forEach(i -> 
            IntStream.range(1, n).forEach(j -> 
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
            )
        );
        return dp[m - 1][n - 1];
    }
}