Simple Java Solution


  • 1
    Z
    import java.util.List;
    
    public class Solution {
        public int minimumTotal(List<List<Integer>> triangle) {
            int[][] dp = new int[triangle.size()][];
            for (int i = 0; i < triangle.size(); i++) {
                dp[i] = new int[triangle.get(i).size()];
                for (int j = 0; j < triangle.get(i).size(); j++) {
                    if (i == 0 && j == 0) {
                        dp[i][j] = triangle.get(i).get(j);
                    } else if (j == 0) {
                        dp[i][j] = dp[i - 1][j] + triangle.get(i).get(j);
                    } else if (j == triangle.get(i).size() - 1) {
                        dp[i][j] = dp[i - 1][j - 1] + triangle.get(i).get(j);
                    } else {
                        dp[i][j] = Math.min(dp[i - 1][j - 1] + triangle.get(i).get(j), dp[i - 1][j] + triangle.get(i).get(j));
                    }
                }
            }
     
            int min = Integer.MAX_VALUE;
            for (int num : dp[triangle.size() - 1]) {
                if (num < min) {
                    min = num;
                }
            }
            return min;
        }
    }
    

Log in to reply
 

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