package leetcode;

/**
 * https://leetcode.com/problems/count-square-submatrices-with-all-ones/
 */
public class Problem1277 {
    public int countSquares(int[][] matrix) {
        // TODO
        return 0;
    }

    public static void main(String[] args) {
        Problem1277 prob = new Problem1277();
        System.out.println(prob.countSquares(new int[][]{
            {0, 1, 1, 1},
            {1, 1, 1, 1},
            {0, 1, 1, 1}
        })); // 15
        System.out.println(prob.countSquares(new int[][]{
            {1, 0, 1},
            {1, 1, 0},
            {1, 1, 0}
        })); // 7
    }
}

@@ -178,38 +178,96 @@
     
-// TODO%0A        return
+int maxRow = matrix.length;%0A        int maxCol = maxRow %3E 0 ? matrix%5B0%5D.length :
  0;%0A    
 %7D%0A%0A 
@@ -266,399 +266,1052 @@
     
-%7D%0A%0A
     
-public static void main(String%5B%5D args) %7B%0A        Problem1277 prob = new Problem1277();%0A        System.out.println(prob.countSquares(new int%5B%5D%5B%5D%7B%0A            %7B0, 1, 1, 1%7D,%0A            %7B1, 1, 1, 1%7D,%0A            %7B0, 1, 1, 1%7D%0A        %7D)); // 15%0A        System.out.println(prob.countSquares(new int%5B%5D%5B%5D%7B%0A            %7B1, 0, 1%7D,%0A            %7B1, 1, 0%7D,%0A            %7B1, 1, 0%7D%0A        %7D)); // 7
+int answer = 0;%0A        Integer%5B%5D%5B%5D memo = new Integer%5BmaxRow%5D%5BmaxCol%5D;%0A        for (int i = 0; i %3C maxRow; i++) %7B%0A            for (int j = 0; j %3C maxCol; j++) %7B%0A                answer += countSquares(matrix, maxRow, maxCol, i, j, memo);%0A            %7D%0A        %7D%0A        return answer;%0A    %7D%0A%0A    private static int countSquares(int%5B%5D%5B%5D matrix, int maxRow, int maxCol, int row, int col,%0A                                    Integer%5B%5D%5B%5D memo) %7B%0A        if (row %3C 0 %7C%7C row == maxRow %7C%7C col %3C 0 %7C%7C col == maxCol) %7B%0A            return 0;%0A        %7D%0A        if (memo%5Brow%5D%5Bcol%5D != null) %7B%0A            return memo%5Brow%5D%5Bcol%5D;%0A        %7D%0A        if (matrix%5Brow%5D%5Bcol%5D == 1) %7B%0A            int a = countSquares(matrix, maxRow, maxCol, row + 1, col, memo);%0A            int b = countSquares(matrix, maxRow, maxCol, row, col + 1, memo);%0A            int c = countSquares(matrix, maxRow, maxCol, row + 1, col + 1, memo);%0A            int min = Math.min(a, Math.min(b, c)) + 1;%0A            memo%5Brow%5D%5Bcol%5D = min;%0A            return min;%0A        %7D%0A        return 0;
 %0A   

Solve problem 1277