题目如下:
Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path. Note: You can only move either down or right at any point in time. Example: Input: [ [1,3,1], [1,5,1], [4,2,1] ] Output: 7 Explanation: Because the path 1→3→1→1→1 minimizes the sum.
64. Minimum Path Sum
给定一个m*n的二维矩阵,让我们找到从左上角到右下角的最小路径和。这道题可以用动态规划解决。设在grid[i][j]的最小路径和为dp[i][j],状态转移方程为:
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j] i > 0, j > 0
实现代码如下:
class Solution { public int minPathSum(int[][] grid) { if (grid == null || grid[0] == null) { return 0; } int x = grid.length; int y = grid[0].length; int[][] dp = new int[x][y]; dp[0][0] = grid[0][0]; for (int i = 1; i < x; i++) { dp[i][0] = dp[i - 1][0] + grid[i][0]; } for (int j = 1; j < y; j++) { dp[0][j] = dp[0][j - 1] + grid[0][j]; } for (int i = 1; i < x; i++) { for (int j = 1; j < y; j++) { dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]; } } return dp[x - 1][y - 1]; } }
- 本文固定链接: https://weiguangli.com/archives/452
- 转载请注明: lwg0452 于 Weiguang的博客 发表
捐 赠如果您觉得这篇文章有用处,请支持作者!鼓励作者写出更好更多的文章!