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;
}
}