[Leetcode] Triangle 三角形

jayce 發布于2019-08-14 12:23 / 2218人閱讀

摘要：動態規劃復雜度時間空間思路這題我們可以從上往下依次計算每個節點的最短路徑，也可以自下而上。自下而上要簡單一些，因為我們只用在兩個下方元素中選一個較小的，就能得到確定解。

Triangle

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).

動態規劃 復雜度

時間 O(NM) 空間 O(1)

思路

這題我們可以從上往下依次計算每個節點的最短路徑，也可以自下而上。自下而上要簡單一些，因為我們只用在兩個下方元素中選一個較小的，就能得到確定解。如果將上一層的累加和存在一個一維數組里，則可以只用O(n)空間，但實際上我們可以直接in place在輸入list中修改值，就可以不用額外空間了。

代碼

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

GPU云服務器云服務器 Triangle LeetCode pascal_triangle LeetCode_String

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

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

leetcode # 118:Pascal's Triangle 楊輝三角

摘要：楊輝三角給定一個非負整數，生成楊輝三角的前行。在楊輝三角中，每個數是它左上方和右上方的數的和。另外可以在內層循環加判斷在不等于時才加上，這樣可省略代碼段，但是這個會在每次進入第一次循環后判斷一次。本著減少資源消耗的原則，應當提到外面。 118:Pascals Triangle 楊輝三角 Given a non-negative integer numRows, generate the...

CKJOKER 2019-07-31 10:37 評論0 收藏0
leetcode # 118:Pascal's Triangle 楊輝三角

摘要：楊輝三角給定一個非負整數，生成楊輝三角的前行。在楊輝三角中，每個數是它左上方和右上方的數的和。另外可以在內層循環加判斷在不等于時才加上，這樣可省略代碼段，但是這個會在每次進入第一次循環后判斷一次。本著減少資源消耗的原則，應當提到外面。 118:Pascals Triangle 楊輝三角 Given a non-negative integer numRows, generate the...

gggggggbong 2019-08-16 18:23 評論0 收藏0
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] Pascal's Triangle 楊輝三角形

摘要：迭代法復雜度時間空間思路簡單的按照楊輝三角形的規則計算就行了。代碼加入第一個加入中間的數加入最后一個逆序相加法復雜度時間空間思路同樣用迭代的方法，根據上一層的值算下一層，不過這里每一層都在同一個上操作。 Pascals Triangle I Given numRows, generate the first numRows of Pascals triangle. For examp...

Berwin 2019-08-14 12:37 評論0 收藏0
LeetCode 118：楊輝三角 II Pascal's Triangle II

摘要：公眾號愛寫作者愛寫給定一個非負索引，其中，返回楊輝三角的第行。在楊輝三角中，每個數是它左上方和右上方的數的和。示例輸入輸出進階你可以優化你的算法到空間復雜度嗎解題思路和之前寫的那篇號楊輝三角基本類似。公眾號：愛寫bug（ID：icodebugs）作者：愛寫bug 給定一個非負索引 k，其中 k ≤ 33，返回楊輝三角的第 k 行。 Given a non-negative index...

KaltZK 2019-08-16 18:29 評論0 收藏0