package com.ljp.test.leetcode;
/**
* <b>64. 最小路径和
*
*
* 给定一个包含非负整数的 mxn 网格grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
*
* 说明：每次只能向下或者向右移动一步。
*
*
* 示例 1：
*
*
* 输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
* 输出：7
* 解释：因为路径 1→3→1→1→1 的总和最小。
* 示例 2：
*
* 输入：grid = [[1,2,3],[4,5,6]]
* 输出：12
*
* 提示：
*
* m == grid.length
* n == grid[i].length
* 1 <= m, n <= 200
* 0 <= grid[i][j] <= 100
*
* 来源：力扣（LeetCode）
* 链接：<a href="https://leetcode.cn/problems/minimum-path-sum">64. 最小路径和
* 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*
* @author luojunping
* @since 2023-03-09
*/
public class Number0064{
public static void main(String[] args) {
int[][] nums1 ={{1, 3, 1}, {1, 5, 1}, {4, 2, 1}};
int[][] nums2 ={{1, 2, 3}, {4, 5, 6}};
System.out.println(DynamicPlanning.minPathSum(nums1));
System.out.println(DynamicPlanning.minPathSum(nums2));
}
/**
* 动态规划
*/
private static class DynamicPlanning{
public static int minPathSum(int[][] nums) {
int m = nums.length;
int n = nums[0].length;
int[][] dp =new int[m][n];
dp[0][0] = nums[0][0];
for (int i =1; i < m; i++) {
dp[i][0] = dp[i -1][0] + nums[i][0];
}
for (int i =1; i < n; i++) {
dp[0][i] = dp[0][i -1] + nums[0][i];
}
for (int i =1; i < m; i++) {
for (int j =1; j < n; j++) {
int minimum = Math.min(dp[i -1][j], dp[i][j -1]);
dp[i][j] = minimum + nums[i][j];
}
}
return dp[m -1][n -1];
}
}
}
