成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

[LintCode/LeetCode] Minimum Path Sum

CntChen / 2348人閱讀

摘要：遍歷整個(gè)矩陣，對(duì)于，取上方和左邊較小值，與相加可得該點(diǎn)最小值。

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

遍歷整個(gè)矩陣，對(duì)于dp[i][j]，取上方dp[i-1][j]和左邊dp[i][j-1]較小值，與grid[i][j]相加可得該點(diǎn)最小值。

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];
    }
}

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/65788.html

相關(guān)文章

  • [LintCode/LeetCode] Triangle

    摘要：第一種方法是很早之前寫的，先對(duì)三角形兩條斜邊賦值，和分別等于兩條斜邊上一個(gè)點(diǎn)的和與當(dāng)前點(diǎn)的和。然后套用動(dòng)規(guī)公式進(jìn)行橫縱坐標(biāo)的循環(huán)計(jì)算所有點(diǎn)的，再遍歷最后一行的，找到最小值即可。 Problem Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacen...

    劉德剛 評(píng)論0 收藏0

  • [LintCode/LeetCode] Binary Tree Maximum Path Sum

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

    cnTomato 評(píng)論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 評(píng)論0 收藏0

  • [LintCode/LeetCode] Find Minimum in Rotated Sorted

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

    cgh1999520 評(píng)論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 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<