A simple top-down dp solution


  • 0
        public int minimumTotal(List<List<Integer>> triangle) {
            if(triangle.size() == 0) {
                return 0;
            }
            int[] buffer = new int[triangle.size()];
            for(int i = 0; i < triangle.size(); ++i) {
                if(i == 0)  {
                    buffer[0] = triangle.get(0).get(0);
                } else {
                    int level = triangle.get(i).size() - 1;
                    for(int j = level; j >= 0; --j) {
                        if(j == level) {
                            buffer[level] = buffer[level - 1] + triangle.get(level).get(level);
                        } else if(j == 0) {
                            buffer[0] = buffer[0] + triangle.get(level).get(0);
                        } else {
                            buffer[j] = Math.min(buffer[j], buffer[j-1]) + triangle.get(level).get(j);
                        }
                    }
                }
            }
            int min = Integer.MAX_VALUE;
            for(int sum : buffer) {
                min = Math.min(sum, min);
            }
            return min;
        }
    

Log in to reply
 

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