1277. 统计全为 1 的正方形子矩阵.md

1277. 统计全为 1 的正方形子矩阵

• 动态规划

/**
 *
 * @description 思考了很久,也许这么思考会更容易理解(我无法一下理解最大边长):
 *              dp[row][col] = k,表示(row, col)这个位置处于一个正方形的右下角的时候
 *              它最大能组一个k x k的正方形,注意我说的是最大能组k x k的正方形,那我是不是还能组(k-1) x (k-1), (k-2) x (k-2)这样的正方形呢!
 *              因此(row, col)这个点作为正方形的右下角时可以组成k个正方形,同意这个观点吗?
 *              再深入理解一下: 以(row, col)为末端的垂直方向,水平方向,左上对角线方向上最多都会有k个连续的1.
 *              于是,动态转移公式就有:
 *                  dp[row][col] = min(
 *                      matrix[row - 1][col - 1], // 说明左上边的对角线上可以最多可以提供这么多个1给我
 *                      matrix[row - 1][col], // 说明上面最多可以提供这么多个1给我
 *                      matrix[row][col - 1], // 说明左边最多可以提供这么多个1给我
 *                  ) + 1; (约束条件: row > 0 && col > 0 && matrix[row][col] === 1)
 * @param {number[][]} matrix
 * @return {*}  {number}
 */
 function countSquares(matrix: number[][]): number {

    const rows: number = matrix.length,
        cols: number = matrix[0].length;

    let count: number = 0;

    for (let row = 0; row < rows; ++row) {
        for (let col = 0; col < cols; ++col) {
            if (row && col && matrix[row][col]) {
                matrix[row][col] = Math.min(
                    matrix[row - 1][col - 1],
                    matrix[row - 1][col],
                    matrix[row][col - 1],
                ) + 1;
            }
            count += matrix[row][col];
        }
    }

    return count;
};