Java DP solution


  • 0
    M
    public class Solution {
        public int minimumTotal(List<List<Integer>> triangle) {
            if(triangle==null) return 0;
            final int N = triangle.size();
            int[][] dp = new int[N][N];
            for(int i=0; i<N; i++)
            	for(int j=0; j<=i; j++)
            		dp[i][j] = Integer.MAX_VALUE;
            return dfs(0, 0, triangle, dp);
        }
        private int dfs(int row, int index, List<List<Integer>> triangle, int[][] dp){
        	if(dp[row][index]<Integer.MAX_VALUE) return dp[row][index];
        	List<Integer> cur = triangle.get(row);
        	int ele = cur.get(index);
            if(row+1 == triangle.size()) {
                dp[row][index] = ele;
                return ele;
            }
            int min = Integer.MAX_VALUE;
            int l = dfs(row+1, index, triangle, dp)+ele;
            int r = dfs(row+1, index+1, triangle, dp)+ele;
            if(l<r) min = Math.min(min, l);
            else min = Math.min(min, r);
            dp[row][index] = Math.min(dp[row+1][index],dp[row+1][index+1])+ ele;
            return min;
        }
    }
    

Log in to reply
 

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