文章目錄

• 1 題目理解
• 2 解題
• • 2.1 動態規劃
  • 2.2 優化空間
  • 2.3進一步優化空間

1 題目理解

Given a triangle array, return the minimum path sum from top to bottom.
For each step, you may move to an adjacent number on the row below.

輸入：一個三角形數組List<List> triangle
輸出：從頂層走到底層最小路徑和
規則：每次只能從上一層走到下一層的相鄰單元。相鄰單元是指與上一層下標相同，或者上一層下標+1。

Example 1:
Input: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
Output: 11
Explanation: The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

2 解題

2.1 動態規劃

2 3 4 6 5 7 4 1 8 3

用dp[i][j]表示達到第i層第j列位置的最小路勁和。
根據題意，要想達到（i,j）只能通過(i-1,j)或者(i-1,j-1)兩種方式達到。
那動態轉移方程是:$$dp[i][j]=min(dp[i?1][j?1],dp[i?1][j])+triangle[i][j]$$
初始化條件：dp[0][0]=triangle[0][0]
最后結果是在最后一層數組中查找最大值

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

時間復雜度:$O(n^2)$，n是triangle的長度。

2.2 優化空間

仔細觀察我們發現動態轉移方程只與i-1有關系，所以我們可以使用滾動數組來實現。

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

2.3進一步優化空間

方程中計算j的時候只與j和j-1相關。如果我們的只有一個數組int[] dp，那我們可以從右到左計算。
我們計算dp[j]的時候使用了dp[j]和dp[j-1]，
在計算dp[j-1]的時候使用dp[j-1]和dp[j-2]，與dpp[j]無關，所以可以這樣做。

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

總結

以上是生活随笔為你收集整理的120. Triangle的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。