My simple and clear DP solution(JAVA, Do not miss this good solution)


  • 0
    X
    public int minimumTotal(List<List<Integer>> triangle) {
        if(triangle.size() == 0) return 0;
        int index = triangle.size() - 1;
        List<Integer> cur = triangle.get(index--);
        while(index >= 0){
            List<Integer> temp = triangle.get(index--);
            for(int i = 0; i < temp.size(); i++){
                temp.set(i, temp.get(i) + Math.min(cur.get(i), cur.get(i + 1)));
            }
            cur = temp;
        }
        return cur.get(0);
    }

Log in to reply
 

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