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，从最底层递推上去。dp[i][j]表示第i层j个元素为起点的最小路径和。

　　递推公式：dp[i][j]=value[i][j]+min{dp[i+1][j],dp[i+1][j+1};

　　因为每一层只跟下一层相关，所以只需一维状态即可。

 

public class Solution {    public int minimumTotal(List
     
      
       > triangle) {        int n = triangle.size();        int[] dp = new int[n];        for (int i = n - 1; i >= 0; i--) {            for (int j = 0; j <= i; j++) {                if (i == n - 1)                    dp[j] = triangle.get(i).get(j);                else                    dp[j] = triangle.get(i).get(j) + Math.min(dp[j], dp[j + 1]);            }        }        return dp[0];    }    public static void main(String[] args) {        List
       
        
         > triangle = new ArrayList
         
          
           >(); triangle.add(Arrays.asList(new Integer[] { 2 })); triangle.add(Arrays.asList(new Integer[] { 3, 4 })); triangle.add(Arrays.asList(new Integer[] { 6, 5, 7 })); triangle.add(Arrays.asList(new Integer[] { 4, 1, 8, 3 })); System.out.println(new Solution().minimumTotal(triangle)); }}
          
         
        
       
      
     

 

 第二遍记录：

先画二维的，然后根据递推顺序转化成一维的。

 

第三遍记录：

　　二维和一维都要注意纵坐标的范围，不要越界。

　　一维递推的时候注意要 自下而上，自左而右。