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.
Problem Link: https://leetcode.com/problems/triangle/
PS:這里要注意一下"adjacent numbers on the row below"的具體含義肴茄，意思是（從上到下移步）下一個(gè)數(shù)字的行號(hào)是當(dāng)前數(shù)字行號(hào)+1荐捻，且列號(hào) >= 當(dāng)前數(shù)字所在列號(hào)佳遂。例如：triangle[i][j] 只能向 triangle[i+1][j] 和 triangle[i+1][j+1] （在triangle[i+1][...]存在的情況下）移動(dòng)。
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
int n = triangle.size();
/* 1. 申請(qǐng) （n+1）*（n+1） 維的int數(shù)組，
因?yàn)槭菑牡紫蛏嫌?jì)算，最后一列res[n]的時(shí)候，將由res[n+1]列數(shù)組計(jì)算得到;
由于該數(shù)組中每個(gè)元素初始化值都為0枫振，所以不影響結(jié)果。
2. res[i][j] 表示從triangle[i][j] 到 三角形底部的最小路徑和萤彩。
*/
int[][] res = new int[n+1][n+1];
for (int i = n-1; i >=0 ; i--) {
for (int j = 0; j <= i; j++) {
res[i][j] =Math.min(res[i+1][j], res[i+1][j+1]) + triangle.get(i).get(j);
}
}
// 返回值表示從三角形最頂部到最底部的最小路徑和粪滤。
return res[0][0];
}
}
該解決方案時(shí)間復(fù)雜度為o(n2)；
空間復(fù)雜度也為o(n2)乒疏，其中n為三角形的行數(shù)额衙。
PS: 注意題目有明確說明，如果空間復(fù)雜度實(shí)現(xiàn)為o(n)將是一個(gè)加法點(diǎn)怕吴，那至少說明空間復(fù)雜度為o(n)的方法是存在的窍侧。
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
int n = triangle.size();
/* 1. 申請(qǐng) （n+1） 維的int數(shù)組，
因?yàn)槭菑牡紫蛏嫌?jì)算转绷，最后一列res[n]的時(shí)候伟件，將由res[n+1]列數(shù)組計(jì)算得到.
由于該數(shù)組中每個(gè)元素初始化都為0，所以不影響結(jié)果议经。
2. res[j] 表示從triangle[i][j] 行到三角形底部的最小路徑和,其中i將從n-1 到 0 進(jìn)行循環(huán)斧账。
若暫時(shí)不能理解谴返，請(qǐng)先看后續(xù)代碼，在腦海中構(gòu)想過程咧织。
*/
int[] res = new int[n+1];
for (int i = n-1; i >=0 ; i--) {
for (int j = 0; j <= i; j++) {
res[j] =Math.min(res[j], res[j+1]) + triangle.get(i).get(j);// 想象從最后一列開始遍歷嗓袱，并記錄該點(diǎn)到三角形底部的最小路徑和。
}
}
return res[0];
}
}
該解決方案時(shí)間復(fù)雜度為o(n2)习绢；
空間復(fù)雜度為o(n)渠抹，其中n為三角形的行數(shù)。
