**給定一個三角形，找出自頂向下的最小路徑和。**每一步只能移動到下一行中相鄰的結點上。

相鄰的結點 在這里指的是 下標 與 上一層結點下標 相同或者等于 上一層結點下標 + 1 的兩個結點。

例如，給定三角形：

[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
自頂向下的最小路徑和為 11（即，2 + 3 + 5 + 1 = 11）。

二維的動態規劃代碼

class Solution {public int minimumTotal(List<List<Integer>> triangle) {int n=triangle.size(),m=triangle.get(n-1).size();int[][] dp=new int[n][m];//存儲到當前節點的最小路徑總和for(int i=0;i<n;i++)Arrays.fill(dp[i],Integer.MAX_VALUE);dp[0][0]=triangle.get(0).get(0);for(int i=1;i<n;i++)for(int j=0;j<triangle.get(i).size();j++){if(j==0) dp[i][j]=dp[i-1][j]+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 res=Integer.MAX_VALUE;for(int j=0;j<m;j++) res= Math.min(res,dp[n-1][j]);return res;}
}

一維的動態規劃代碼

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