国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

[LintCode/LeetCode] Minimum Path Sum

CntChen / 2338人閱讀

摘要:遍歷整個矩陣,對于,取上方和左邊較小值,與相加可得該點最小值。

Problem

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.

You can only move either down or right at any point in time.

Note

遍歷整個矩陣,對于dp[i][j],取上方dp[i-1][j]和左邊dp[i][j-1]較小值,與grid[i][j]相加可得該點最小值。

Solution
public class Solution {
    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];
    }
}

文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。

轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/65788.html

相關文章

  • [LintCode/LeetCode] Triangle

    摘要:第一種方法是很早之前寫的,先對三角形兩條斜邊賦值,和分別等于兩條斜邊上一個點的和與當前點的和。然后套用動規公式進行橫縱坐標的循環計算所有點的,再遍歷最后一行的,找到最小值即可。 Problem Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacen...

    劉德剛 評論0 收藏0
  • [LintCode/LeetCode] Binary Tree Maximum Path Sum

    摘要:調用函數更新路徑和的最大值,而函數本身需要遞歸,返回的是單邊路徑和。所以函數要返回的是,主函數中返回的卻是最上一層根節點處和的較大值,與之前遍歷過所有路徑的最大值之間的最大值。 Problem Given a binary tree, find the maximum path sum. The path may start and end at any node in the tre...

    cnTomato 評論0 收藏0
  • [LintCode/LeetCode] Minimum Window Substring

    Problem Given a string source and a string target, find the minimum window in source which will contain all the characters in target. Notice If there is no such window in source that covers all charac...

    Corwien 評論0 收藏0
  • [LintCode/LeetCode] Find Minimum in Rotated Sorted

    摘要:排序數組中找最小值或最大值的題目,很明顯可以使用二分法。因此,只判斷終點和中點元素的大小關系即可。這里有一種情況是上述后三個,中點值和末位相等。此時,兩邊同時遞歸,并返回兩邊遞歸值的較小值。當首位和末位重合,說明已夾逼得到最小值。 Find Minimum in Rotated Sorted Array Problem Suppose a sorted array is rotated...

    cgh1999520 評論0 收藏0
  • [LintCode/LeetCode] Integer Replacement

    Problem Given a positive integer n and you can do operations as follow: 1.If n is even, replace n with n/2.2.If n is odd, you can replace n with either n + 1 or n - 1. What is the minimum number of re...

    fyber 評論0 收藏0

發表評論

0條評論

CntChen

|高級講師

TA的文章

閱讀更多
最新活動
閱讀需要支付1元查看
<