class Solution {

    public int minimumTotal(List<List<Integer>> triangle) {

        if(triangle.size() == 0 || triangle == null) return 0;

        int rows = triangle.size();

        int[] dp = new int[rows + 1];

        for(int i = rows - 1; i >= 0 ; i--){

            for(int j = 0; j <= i; j++){

                dp[j] = Math.min(dp[j], dp[j + 1]) + triangle.get(i).get(j);

            }

        }

        return dp[0];

    }

}

class Solution {

    public int numSquares(int n) {

        int[] dp = new int[n + 1];

        Arrays.fill(dp, Integer.MAX_VALUE);

        dp[0] = 0;

        for(int i = 1; i <= n; i++){

            for(int j = 1; j * j <= i; j++){

                dp[i] = Math.min(dp[i], dp[i - j * j] + 1);

            }

        }

        return dp[n];

    }

}