# [improved to 3ms]4ms Java DP solution, please give some suggestions for improvement!

• the solution has been improved to 3ms thanks to the suggestion in answer

``````public class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
/**
* dp[i] denotes the sum of path to ith element on this row
* for every element on this row, dp[i] is calculated according to the dp on previous row
**/
int size = triangle.size(); //pre-store the size of triangle in "size", could improve 1ms of total time
//if no rows in triangle
if(size==0) return 0;
//if only one row in triangle
if(size==1) return triangle.get(0).get(0);
int[] dp = new int[size];
dp[0] = triangle.get(0).get(0);
for(int i = 1;i< size;i++){
List<Integer> thisRow = triangle.get(i);//pre-store the list of the current row, could improve 1ms of total time
int[] pre = dp.clone(); //handy way to copy an array with primitive type
dp[0] = pre[0]+thisRow.get(0);
dp[i] = pre[i-1]+thisRow.get(i);
for(int j = 1;j<i;j++){
dp[j] = Math.min(pre[j-1],pre[j])+thisRow.get(j);
}
}
// find the minimum value in dp as the minimum path
int min = dp[0];
for(int i: dp){
if(i<min) min = i;
}
return min;
}
``````

}

• This is my 3ms solution:

``````    int SIZE=triangle.size();
if (SIZE == 0)
return 0;
if (triangle.size() == 1)
return triangle.get(0).get(0);

int[] keep = new int[SIZE];
keep[0]=triangle.get(0).get(0);

for(int i=1;i<SIZE;i++){
List<Integer> thisrow=triangle.get(i);
int[] temp = keep.clone();
keep[0]=temp[0]+thisrow.get(0);
keep[i]=temp[i-1]+thisrow.get(i);
for(int j=1;j<i;j++){
keep[j]=thisrow.get(j)+Math.min(temp[j-1], temp[j]);
}
}

int min=keep[0];
for(int k:keep){
if(k<min) min=k;
}
return min;``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.