題目鏈接 => 戳這里
題目解析
這道題其實(shí)有一點(diǎn)是需要另外拿出來講的缭裆，對(duì)比跑樓梯陈莽，跑樓梯的最后狀態(tài)求解渤昌，我們是很明確要求解的節(jié)點(diǎn)的，但是這道題走搁，如果我們自頂向下求解的話独柑，我們會(huì)發(fā)現(xiàn)我們并不是很明確究竟最后要返回dp[i][j]中的哪個(gè)節(jié)點(diǎn)，當(dāng)然也可以做到私植，因?yàn)槲覀冎雷詈蟮慕庖欢ㄊ窃谧詈笠恍兄械哪硞€(gè)數(shù)忌栅，所以我們只需要對(duì)最后一行的dp值進(jìn)行排序，然后返回最小的值即可曲稼。但是我們自底向上的話索绪，最終的求解節(jié)點(diǎn)就明確是dp[0][0]了；
動(dòng)態(tài)規(guī)劃四步走：
1.問題拆解：
關(guān)鍵條件是每一步只能移動(dòng)到下一行的相鄰節(jié)點(diǎn)贫悄，也就是說經(jīng)過dp[i][j]的節(jié)點(diǎn)瑞驱，只可能經(jīng)過dp[i+1][j]或者dp[i+1][j+1]，那也就是說對(duì)dp[i][j]的最小值求解就拆解成了對(duì)dp[i+1][j]和dp[i+1][j+1]中的最小值加上[i][j]節(jié)點(diǎn)本身的值了窄坦；
2.狀態(tài)定義：
節(jié)點(diǎn)[i][j]的路徑最小值 = Min(dp[i+1][j]唤反，dp[i+1][j+1]) + 節(jié)點(diǎn)[i][j]本身的值；
3.遞推方程：
dp[i][j] = Math.Min(dp[i+1][j], dp[i+1][j+1]) + triangle[i][j];
4.實(shí)現(xiàn)：
狀態(tài)值初始化：最后一行的數(shù)據(jù)需要自行初始化
解法
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
int size = triangle.size();
// 基本操作:聲明狀態(tài)方程數(shù)組
int[][] dp = new int[size][size];
// 狀態(tài)值初始化
List<Integer> lastRow = triangle.get(size-1);
for (int i = 0; i < lastRow.size(); i++) {
dp[size-1][i] = lastRow.get(i);
}
for (int i = size - 2; i >= 0; i--) {
List<Integer> tmp = triangle.get(i);
for (int j = 0; j < i+1; j++) {
dp[i][j] = Math.min(dp[i+1][j], dp[i+1][j+1]) + tmp.get(j);
}
}
return dp[0][0];
}
}
