leetcode 120. Triangle
Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
For example, given the following triangle
[ [2], [3,4], [6,5,7], [4,1,8,3]]
The minimum path sum from top to bottom is 11
(i.e., 2 + 3 + 5 + 1 = 11).
动态规划,dp[i][j]表示第i行第j列元素到起点的最短路径。那么
dp[i][j]=triangle.get(i).get(j)+Math.min(dp[i-1][j-1],dp[i-1][j]); 要主要特殊值:每一行最开始和最后元素。
public class Solution { public int minimumTotal(List
> triangle) { if (triangle.size()==0){ return 0; } Integer[][] dp=new Integer[triangle.size()][]; for (int i=0;i dp[len-1][i]){ min=dp[len-1][i]; } } return min; }}