Count Square Submatrices with All Ones

给一个1和0的2d数组, 求有几个1围成的正方形. 这个题是dp做. dp[i][j] 代表以i和j为右下角的正方形的个数, 那么推导式: dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1])), when dp[i][j] == 1. 这个推导式是通过观察得来的. 比如[1,1][1,1], 那么是5, 4个side = 1的和一个side = 2的正方形. 如果dp是[2,2][2,2], 那么则说明数组是[1,1,1][1,1,1][1,1,1].

class Solution {
    public int countSquares(int[][] matrix) {
        if(matrix == null)
             return 0;
        int ret = 0;
        for(int i = 0; i < matrix.length; i++) {
            for(int j = 0; j < matrix[0].length; j++) {
                if(matrix[i][j] == 0)
                    continue;
                if(i >= 1 && j >= 1){
                    matrix[i][j] = Math.min(
                     Math.min(matrix[i-1][j-1],matrix[i-1][j]),
                        matrix[i][j-1])+1;
                } 
                ret += matrix[i][j];
            }
        }
        return ret;
    }
}