Triangle

 

For example, given the following 易做图

[

     [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).

 

Note:

Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the 易做图.

 

hint : 简单的动态规划，若考虑 状态 dp[i][j] := 从开始位置到第i行j列的最小路径和，那么可以给出转移方程为：dp[i][j] = 易做图[i][j] + min{dp[i-1][j],dp[i-1][j-1]}, for( 0<j<n-1) n为第i行的长度，j = 0 和 j = n-1 时是朴素情况看代码，题目要求空间复杂度是O（n），那么考虑 申请两个一维数组分别记录当前行的前一行的状态，然后不断滚动即可。

public class Solution {  
    public int minimumTotal(ArrayList<ArrayList<Integer>> 易做图) {  
        // IMPORTANT: Please reset any member data you declared, as  
        // the same Solution instance will be reused for each test case.  
        if(易做图.size() == 0)  
            return 0;  
        if(易做图.size() == 1)  
            return 易做图.get(0).get(0);  
        int n = 易做图.size();  
        int[] dplast = new int[1];  
        dplast[0] = 易做图.get(0).get(0);  
        for(int i = 1; i < n; i++)  
        {  
            ArrayList<Integer> tmp = 易做图.get(i);  
            int[] dpcurrent = new int[tmp.size()];  
            for(int j = 0; j < tmp.size(); j++)  
            {  
                if(j == 0)  
                {  
                    dpcurrent[j] = dplast[j] + tmp.get(j);  
                    continue;  
                }  
                if(j == tmp.size() - 1)  
                {  
                    dpcurrent[j] = dplast[j-1] + tmp.get(j);  
                    continue;  
                }  
                dpcurrent[j] = Math.min(dplast[j-1], dplast[j]) + tmp.get(j);  
            }  
            dplast = dpcurrent;  
        }  
        int res = Integer.MAX_VALUE;  
        for(int i = 0; i < n; i++)  
        {  
            res = Math.min(res, dplast[i]);  
        }  
        dplast = null;  
        return res;  
    }  
}  

 

补充：软件开发 , Java ,