题目链接
思路
分析动态规划题目的时候只需要考虑最后一个阶段，因为所有的阶段转化都是相同的，考虑最后一个阶段容易发现规律
在数组的动态规划问题中，一般 dp[i] 都是表示以 nums 以前 i 个元素组成（即 nums[i - 1]）的状态；dp[i][j] 分别表示以 nums1 前 i 个元素（即 nums1[i - 1]）组成和以 nums2 前 j 个元素（即 nums2[j - 1]）组成的状态，以此类推
字符串也是个数组，是字符数组
表示状态
状态表示就是靠猜，但是会有猜的套路，一般都是通过最终结果和数组数量来猜
这道题的思路和【DP】LeetCode 221. 最大正方形基本一致
因为在本题中我们使用 \(dp[i][j]\) 表示以 \((i, j)\) 为右下角的正方形的个数，同时 \(dp[i][j]\) 也表示以 \((i, j)\) 为右下角的正方形的最大边长，因为这里面有边长为 \(1, 2, ..., dp[i][j]\) 的正方形各一个
找状态转移方程
思考的方向是：大问题的最优解怎么由小问题的最优解得到
参考221题，状态转移方程完全一致
\[dp[i][j] = \left\{ \begin{aligned} & min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1, & matrix[i][j] = 1, \\ & 0, & matrix[i][j] = 0. \end{aligned} \right. \]因为 \(dp[i][j]\) 表示以 \((i, j)\) 为右下角的正方形的个数，而题目要求求的是总数，所以最后要对 \(dp[i][j]\) 进行求和，这就是最终结果。
注意：这样加和是不会重复计算正方形数量的，因为我们是按照每个坐标作为正方形右下角进行统计，这样能保证每个正方形的定位是独一无二的。
边界处理
对第一行和第一列进行初始化：
\[dp[i][j] = \left\{ \begin{aligned} & 1, & matrix[i][j] = '1', \\ & 0, & matrix[i][j] = '0'. \end{aligned} \right. \]代码
dp数组版
class Solution {
public int countSquares(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
// dp[i][j] 表示以 (i, j) 为右下角的正方形的个数
// 同时 dp[i][j] 也表示以 (i, j) 为右下角的正方形的最大边长
// 因为这里面有边长为 1, 2, ..., dp[i][j] 的正方形各一个
int[][] dp = new int[m][n];
for(int i = 0; i < m; i++){
dp[i][0] = matrix[i][0];
}
dp[0] = matrix[0];
for(int i = 1; i < m; i++){
for(int j = 1; j < n; j++){
if(matrix[i][j] == 1){
dp[i][j] = Math.min(
dp[i - 1][j],
Math.min(dp[i][j - 1], dp[i - 1][j - 1])
) + 1;
}
}
}
int result = 0;
for(int i = 0; i < m; i++){
result += Arrays.stream(dp[i]).sum();
}
return result;
}
}