5.5
明知道这种题目里边，递归的方法是过不了的，但还是不死心的用了递归，果然没有过呢。
呵呵呵呵呵。
public class Solution { /** * @param triangle: a list of lists of integers. * @return: An integer, minimum path sum. */ public int minimumTotal(int[][] triangle) { // write your code here int length = triangle.length; if(length == 0){ return 0; } //System.out.println("length:" + length); if(length == 1){ return triangle[0][0]; } int size = triangle[length-1].length; int[][] flag = triangle; setFlag(triangle,flag,length,size); return flag[0][0]; } //给出一个数组，以及开始结束的地方，获得当前数组的最小值 // 果然啊果然，用递归就会又超时了呢。 /* public int getMin(int[][] triangle,int i,int j){ if(i < j){ return 0; } int m = triangle.length;//获取行数 int n = triangle[m-1].length;//获取最大的列数 if( i == m-1){ return triangle[i][j]; } int x = getMin(triangle,i+1,j); int y = getMin(triangle,i+1,j+1); return triangle[i][j] + Math.min(x,y); } */ public void setFlag(int[][] triangle,int[][] flag,int m,int n){ // m表示行，n表示列 flag[m-1] = triangle[m-1]; if(m <= 1){ return; } for(int i = m-2; i >= 0; i--){ for(int j = 0; j<=i; j++){ flag[i][j] = triangle[i][j] + Math.min(flag[i+1][j],flag[i+1][j+1]); } } } }