[LeetCode] 120. Triangle

stormjun 發布于2019-08-16 13:51 / 1606人閱讀

Problem

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Note:

Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

Bottom-top DP

class Solution {
    public int minimumTotal(List> triangle) {
        int[] dp = new int[triangle.size()+1];
        for (int i = triangle.size()-1; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                dp[j] = Math.min(dp[j], dp[j+1]) + triangle.get(i).get(j);
            }
        }
        return dp[0];
    }
}

Non Extra Space DP

class Solution {
    public int minimumTotal(List> triangle) {
        int len = triangle.size();
        for (int i = len-2; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                int preMin = Math.min(triangle.get(i+1).get(j), triangle.get(i+1).get(j+1));
                int curMin = preMin + triangle.get(i).get(j);
                triangle.get(i).set(j, curMin);
            }
        }
        return triangle.get(0).get(0);
    }
}

GPU云服務器云服務器 Triangle LeetCode pascal_triangle 120美金

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

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

leetcode-120-Triangle-等腰三角形

摘要：題目示例題目解析此題是等腰三角形，上下之間的關系簡化為上下相鄰的三個數，相鄰，大小關系是在下方二選一上方的數值，必然正確。根據此思路，可以或者，由于可以簡化，所以動態規劃方法。代碼普通代碼，較慢動態規劃，簡練題目： Given a triangle, find the minimum path sum from top to bottom. Each step you may mov...

MarvinZhang 2019-07-30 16:07 評論0 收藏0
[Leetcode] Triangle 三角形

摘要：動態規劃復雜度時間空間思路這題我們可以從上往下依次計算每個節點的最短路徑，也可以自下而上。自下而上要簡單一些，因為我們只用在兩個下方元素中選一個較小的，就能得到確定解。 Triangle Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent ...

jayce 2019-08-14 12:23 評論0 收藏0
[LintCode/LeetCode] Triangle

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

劉德剛 2019-08-14 15:28 評論0 收藏0
css繪制各種形狀圖形（第二版）

摘要：雖然我們現在大都使用字體圖標或者圖片，似乎使用來做圖標意義不是很大，但怎么實現這些圖標用到的一些技巧及思路是很值得我們的學習。雖然我們現在大都使用字體圖標或者svg圖片，似乎使用 CSS 來做圖標意義不是很大，但怎么實現這些圖標用到的一些技巧及思路是很值得我們的學習。一、實心圓 showImg(https://segmentfault.com/img/bVbsV6v?w=171&h...

CoreDump 2019-08-30 10:58 評論0 收藏0