?LeetCode刷題實戰(zhàn)64：最小路徑和
算法的重要性，我就不多說了吧，想去大廠，就必須要經(jīng)過基礎知識和業(yè)務邏輯面試+算法面試。所以，為了提高大家的算法能力，這個公眾號后續(xù)每天帶大家做一道算法題，題目就從LeetCode上面選 ！
今天和大家聊的問題叫做?最小路徑和，我們先來看題面：
https://leetcode-cn.com/problems/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.
題意
輸入:
[
??[1,3,1],
??[1,5,1],
??[4,2,1]
]
輸出: 7
解釋: 因為路徑 1→3→1→1→1?的總和最小。
解題
public?int?minPathSum(int[][] grid)?{
????int?m = grid.length, n = grid[0].length;
????int[][] dp = new?int[m][n];
????dp[0][0] = grid[0][0];
????//第一列只能從上面走下來
????for?(int?i = 1; i < m; i++) {
????????dp[i][0] = dp[i - 1][0] + grid[i][0];
????}
????//第一行只能從左邊走過來
????for?(int?i = 1; i < n; i++) {
????????dp[0][i] = dp[0][i - 1] + grid[0][i];
????}
????for?(int?i = 1; i < m; i++) {
????????for?(int?j = 1; j < n; j++) {
????????????//遞推公式，取從上面走下來和從左邊走過來的最小值+當前坐標的值
????????????dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
????????}
????}
????return?dp[m - 1][n - 1];
}
上期推文：
評論
圖片
表情