給定一個三角形各聘，找出自頂向下的最小路徑和寓娩。每一步只能移動到下一行中相鄰的結(jié)點上。
例如堕仔，給定三角形：
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
自頂向下的最小路徑和為 11（即擂橘，2 + 3 + 5 + 1 = 11）。說明：
如果你可以只使用 O(n) 的額外空間（n 為三角形的總行數(shù)）來解決這個問題摩骨，那么你的算法會很加分通贞。
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/triangle
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)恼五，非商業(yè)轉(zhuǎn)載請注明出處昌罩。
首先會想到的用DFS深度優(yōu)先搜索，但是可以更簡潔的使用動態(tài)規(guī)劃
動態(tài)規(guī)劃分析：
- 從底向上灾馒，記錄底部到當(dāng)前的最短距離f(row, column)
- f(row, column) = min(f(row + 1, column), f(row + 1, column + 1)) + triangle[row, column]
class Solution {
/**
* 動態(tài)規(guī)劃：
* 1. 從底向上茎用，記錄底部到當(dāng)前的最短距離f(row, column)
* 2. f(row, column) = min(f(row + 1, column), f(row + 1, column + 1)) + triangle[row, column]
*
* @param triangle
* @return
*/
public int minimumTotal(List<List<Integer>> triangle) {
// 數(shù)組重復(fù)使用
int[] minSum = new int[triangle.size() + 1];
for (int row = triangle.size() - 1; row >= 0; row--) {
for (int column = 0; column < triangle.get(row).size(); column++) {
minSum[column] = Math.min(minSum[column], minSum[column + 1]) + triangle.get(row).get(column);
}
}
return minSum[0];
}
}
運(yùn)行效率
