leetcode解题方案--064--Minimum Path Sum

本文主要是介绍leetcode解题方案--064--Minimum Path Sum，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

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 1:
[[1,3,1],
[1,5,1],
[4,2,1]]
Given the above grid map, return 7. Because the path 1→3→1→1→1 minimizes the sum.

分析

emmmmm
没得说
dp
这里写代码片

class Solution {public static int minPathSum(int[][] grid) {int[] dp = new int[grid[0].length];dp[0] = grid[0][0];for (int i = 1; i<grid[0].length;i++) {dp[i] = dp[i-1] + grid[0][i];}for (int i = 1; i<grid.length; i++) {for (int j = 0; j<grid[0].length; j++) {if (j ==0) {dp[j] = dp[j]+grid[i][j];} else {dp[j] = Math.min(dp[j],dp[j-1])+grid[i][j];}}}return dp[dp.length-1];}
}

这篇关于leetcode解题方案--064--Minimum Path Sum的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---