受限网格中可构造正方形数量计算及时间复杂度优化

核心DP定义 #

• 定义二维数组dp[i][j]：表示以网格第i行第j列单元格为右下角的全可用正方形的最大边长

状态转移规则 #

• 若当前单元格grid[i][j]为不可用的'x'，则dp[i][j] = 0，无法构成任何以该点为右下角的正方形
• 若当前单元格为可用的' '：
  • 边界情况：i=0（第一行）或j=0（第一列）时，dp[i][j] = 1，最多只能构成1x1的正方形
  • 非边界情况：dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
    原理说明：要构成更大的正方形，必须同时满足上方、左方、左上方三个方向的正方形边界都有效，取三者的最小边长再加1就是当前可支持的最大边长

计数规则 #

每个dp[i][j]的数值恰好等于以(i,j)为右下角的正方形的总数量：比如dp[i][j] = 3时，对应1个3x3、1个2x2、1个1x1共3个正方形，将所有dp[i][j]的值累加即可得到网格中所有正方形的总数。 #

import java.io.*;

class Main {
  public static void main(String[] args) throws Exception {
    char[][] grid = {{'x', ' ', ' ', ' '}, {' ', ' ', ' ', ' '}, {' ', ' ', ' ', ' '}, {' ', ' ', ' ', 'x'}};
    int answer = getCount(grid);
    System.out.println(answer); // 输出23，符合示例结果
  }

  private static int getCount(char[][] grid) {
    int height = grid.length;
    if(height == 0) return 0;
    int width = grid[0].length;
    int[][] dp = new int[height][width];
    int total = 0;

    // 初始化第一行
    for(int j = 0; j < width; j++) {
      if(grid[0][j] == ' ') {
        dp[0][j] = 1;
        total += dp[0][j];
      }
    }

    // 初始化第一列（跳过(0,0)避免重复计算）
    for(int i = 1; i < height; i++) {
      if(grid[i][0] == ' ') {
        dp[i][0] = 1;
        total += dp[i][0];
      }
    }

    // 遍历剩余单元格
    for(int i = 1; i < height; i++) {
      for(int j = 1; j < width; j++) {
        if(grid[i][j] == ' ') {
          dp[i][j] = Math.min(Math.min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + 1;
          total += dp[i][j];
        } else {
          dp[i][j] = 0;
        }
      }
    }
    return total;
  }
}

上述实现空间复杂度为O(MN)，如果要进一步优化，可以将二维DP数组压缩为一维数组：因为计算当前行的dp[j]时，只需要上一行的dp[j]、当前行的dp[j-1]、以及上一行的dp[j-1]三个值，用临时变量存储上一行的dp[j-1]即可，优化后空间复杂度为O(N)，时间复杂度保持O(MN)不变。

内容的提问来源于stack exchange，提问作者devi prasad