資訊專(zhuān)欄INFORMATION COLUMN
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 DPclass 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);
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/72458.html
摘要：題目示例題目解析此題是等腰三角形，上下之間的關(guān)系簡(jiǎn)化為上下相鄰的三個(gè)數(shù)，相鄰，大小關(guān)系是在下方二選一上方的數(shù)值，必然正確。根據(jù)此思路，可以或者，由于可以簡(jiǎn)化，所以動(dòng)態(tài)規(guī)劃方法。代碼普通代碼，較慢動(dòng)態(tài)規(guī)劃，簡(jiǎn)練 題目： Given a triangle, find the minimum path sum from top to bottom. Each step you may mov...
摘要：動(dòng)態(tài)規(guī)劃復(fù)雜度時(shí)間空間思路這題我們可以從上往下依次計(jì)算每個(gè)節(jié)點(diǎn)的最短路徑，也可以自下而上。自下而上要簡(jiǎ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 ...
摘要：第一種方法是很早之前寫(xiě)的，先對(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...
摘要：雖然我們現(xiàn)在大都使用字體圖標(biāo)或者圖片，似乎使用來(lái)做圖標(biāo)意義不是很大，但怎么實(shí)現(xiàn)這些圖標(biāo)用到的一些技巧及思路是很值得我們的學(xué)習(xí)。 雖然我們現(xiàn)在大都使用字體圖標(biāo)或者svg圖片，似乎使用 CSS 來(lái)做圖標(biāo)意義不是很大，但怎么實(shí)現(xiàn)這些圖標(biāo)用到的一些技巧及思路是很值得我們的學(xué)習(xí)。 一、實(shí)心圓 showImg(https://segmentfault.com/img/bVbsV6v?w=171&h...
閱讀 1190·2021-11-23 10:05
閱讀 1839·2021-11-12 10:36
閱讀 1886·2019-08-30 15:56
閱讀 1714·2019-08-29 12:32
閱讀 3072·2019-08-28 18:04
閱讀 3457·2019-08-26 12:17
閱讀 2530·2019-08-26 11:35
閱讀 1280·2019-08-23 15:11
