原創(chuàng)公眾號(hào)：bigsai 歡迎加入力扣打卡
文章已收錄在 全網(wǎng)都在關(guān)注的數(shù)據(jù)結(jié)構(gòu)與算法學(xué)習(xí)倉(cāng)庫(kù) 歡迎star

題目描述

力扣120原題
給定一個(gè)三角形 triangle ，找出自頂向下的最小路徑和。

每一步只能移動(dòng)到下一行中相鄰的結(jié)點(diǎn)上。相鄰的結(jié)點(diǎn) 在這里指的是 下標(biāo) 與 上一層結(jié)點(diǎn)下標(biāo) 相同或者等于 上一層結(jié)點(diǎn)下標(biāo) + 1 的兩個(gè)結(jié)點(diǎn)。也就是說(shuō)，如果正位于當(dāng)前行的下標(biāo) i ，那么下一步可以移動(dòng)到下一行的下標(biāo) i 或 i + 1 。

示例 1：

輸入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]] 輸出：11 解釋：如下面簡(jiǎn)圖所示：23 46 5 7 4 1 8 3 自頂向下的最小路徑和為 11（即，2 + 3 + 5 + 1 = 11）。

示例 2：

輸入：triangle = [[-10]] 輸出：-10

提示：

1 <= triangle.length <= 200 triangle[0].length == 1 triangle[i].length == triangle[i - 1].length + 1 -104 <= triangle[i][j] <= 104

進(jìn)階：

你可以只使用 O(n) 的額外空間（n 為三角形的總行數(shù)）來(lái)解決這個(gè)問(wèn)題嗎？

分析

這道題是一道經(jīng)典的動(dòng)態(tài)規(guī)劃的問(wèn)題,但是其具體的處理方法有很多種,但是不同的方法空間和效率略有不同.

自頂向下的思考
自頂向下也是題目給的提示和要求,題目也很簡(jiǎn)單,自頂向下的時(shí)候需要進(jìn)行層層計(jì)算,每層的第一個(gè)和最后一個(gè)需要特殊處理一下.計(jì)算的結(jié)果為該層該節(jié)點(diǎn)最小路徑,正常位置的需要找到疊加到上層的最小路徑(上層前一個(gè)位置和上層同位置的).

所以在具體實(shí)現(xiàn)上我們使用一個(gè)dp[][]的二維數(shù)組來(lái)存儲(chǔ),dp[i][j]表示第i行,第j個(gè)元素的最小路徑值.所以狀態(tài)轉(zhuǎn)移方程為:

dp[i][0]=dp[i-1][0]+arr[0];//j=0的時(shí)候 dp[i][j]=min(dp[i-1][j-1],dp[i-1][j])+arr[j];//0<j<i時(shí)候 dp[i][i]=dp[i-1][j-1]+arr[i];//j=i時(shí)候 因?yàn)樯弦粚舆@個(gè)位置沒(méi)有數(shù)字

計(jì)算完每個(gè)位置的最小路徑之后,只需要在最底層找到最小那個(gè)路徑值返回即可.

具體實(shí)現(xiàn)的代碼為:

class Solution {public int minimumTotal(List<List<Integer>> triangle) {int len=triangle.size();int dp[][]=new int[len][len];dp[0][0]=triangle.get(0).get(0);for(int i=1;i<len;i++){dp[i][0]=dp[i-1][0]+triangle.get(i).get(0);//0號(hào)位置只能從上面來(lái)for(int j=1;j<i;j++){dp[i][j]=Math.min(dp[i-1][j-1],dp[i-1][j])+triangle.get(i).get(j);}dp[i][i]=dp[i-1][i-1]+triangle.get(i).get(i);}int min=dp[len-1][0];for(int i=0;i<len;i++){// System.out.println(dp[len-1][i]);if(min>dp[len-1][i])min=dp[len-1][i];}return min;} }

自底向上的方法
上面是按照自頂向上的方法,這里也可以使用自底向上的方法,反正都是一條最短路徑,從上從下都一樣.當(dāng)然在這里我們dp[]只開(kāi)一維即可,從下往上疊加的時(shí)候只需要找下面和下右面中較小的那個(gè)路徑即可.

而從左向右每一層的遍歷剛好可以使得空間復(fù)用,每一層核心狀態(tài)轉(zhuǎn)移方程為:

dp[j]=triangle[i][j]+min(dp[j],dp[j+1]); //第i層的狀態(tài)轉(zhuǎn)移方程

具體實(shí)現(xiàn)的代碼為:

class Solution {public int minimumTotal(List<List<Integer>> triangle) {int len=triangle.size();int dp[]=new int [len+1];for(int i=len-1;i>=0;i--){for(int j=0;j<=i;j++){dp[j]=triangle.get(i).get(j)+Math.min(dp[j],dp[j+1]);}}return dp[0];} }

原創(chuàng)不易，如果覺(jué)得有所收獲，希望大家點(diǎn)贊、分享、收藏一鍵三連幫忙擴(kuò)散，謝謝！

咱們下次再見(jiàn)！關(guān)注后歡迎加入力扣打卡群(備注力扣 csdn即可)。

總結(jié)

以上是生活随笔為你收集整理的三角形最小路径和(动态规划)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。