[Leetcode] Triangle 三角形

jayce 發(fā)布于2019-08-14 12:23 / 2225人閱讀

摘要：動(dòng)態(tài)規(guī)劃復(fù)雜度時(shí)間空間思路這題我們可以從上往下依次計(jì)算每個(gè)節(jié)點(diǎn)的最短路徑，也可以自下而上。自下而上要簡單一些，因?yàn)槲覀冎挥迷趦蓚€(gè)下方元素中選一個(gè)較小的，就能得到確定解。

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

動(dòng)態(tài)規(guī)劃 復(fù)雜度

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

思路

這題我們可以從上往下依次計(jì)算每個(gè)節(jié)點(diǎn)的最短路徑，也可以自下而上。自下而上要簡單一些，因?yàn)槲覀冎挥迷趦蓚€(gè)下方元素中選一個(gè)較小的，就能得到確定解。如果將上一層的累加和存在一個(gè)一維數(shù)組里，則可以只用O(n)空間，但實(shí)際上我們可以直接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);
    }
}

云服務(wù)器 GPU云服務(wù)器 Triangle LeetCode pascal_triangle LeetCode_String

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

轉(zhuǎn)載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/64446.html

相關(guān)文章

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

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

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

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

gggggggbong 2019-08-16 18:23 評論0 收藏0
leetcode-120-Triangle-等腰三角形

摘要：題目示例題目解析此題是等腰三角形，上下之間的關(guān)系簡化為上下相鄰的三個(gè)數(shù)，相鄰，大小關(guān)系是在下方二選一上方的數(shù)值，必然正確。根據(jù)此思路，可以或者，由于可以簡化，所以動(dòng)態(tài)規(guī)劃方法。代碼普通代碼，較慢動(dòng)態(tài)規(guī)劃，簡練題目： 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 楊輝三角形

摘要：迭代法復(fù)雜度時(shí)間空間思路簡單的按照楊輝三角形的規(guī)則計(jì)算就行了。代碼加入第一個(gè)加入中間的數(shù)加入最后一個(gè)逆序相加法復(fù)雜度時(shí)間空間思路同樣用迭代的方法，根據(jù)上一層的值算下一層，不過這里每一層都在同一個(gè)上操作。 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

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

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