劳务公司网站建设方案,专门做图片的网站,农业电商网站建设,邯郸市丛台区最新疾情【CSDN 每日一练 ★★☆】【动态规划】最小路径和
动态规划
题目
给定一个包含非负整数的 m x n 网格 grid #xff0c;请找出一条从左上角到右下角的路径#xff0c;使得路径上的数字总和为最小。
说明#xff1a;每次只能向下或者向右移动一步。
示例
示例 1#x…【CSDN 每日一练 ★★☆】【动态规划】最小路径和
动态规划
题目
给定一个包含非负整数的 m x n 网格 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.lengthn grid[i].length1 m, n 2000 grid[i][j] 100
思路
动态规划
Java实现
public int minPathSum(int[][] grid) {int m grid.length;int n grid[0].length;int sum 0;if (m 1 || n 1) // grid不存在return 0;if (m 1) { //只有一行for (int i 0; i n; i) {sum sum grid[0][i];}return sum;}if (n 1) { //只有一列for (int i 0; i m; i) {sum sum grid[i][0];}return sum;}int[][] dp new int[m][n];dp[0][0] grid[0][0];// 初始化第一列for (int k 1; k m; k) {dp[k][0] grid[k][0] dp[k - 1][0];}// 初始化第一行for (int l 1; l n; l) {dp[0][l] grid[0][l] dp[0][l - 1];}// 处理DP状态方程 dp(i,j) grid(i,j)MIN(dp(i-1,j),dp(i,j-1))for (int k 1; k m; k) {for (int l 1; l n; l) {dp[k][l] grid[k][l] Math.min(dp[k - 1][l], dp[k][l - 1]);}}return dp[m - 1][n - 1];
}
