Maximal Square

挨个遍历，当前位置作为正方形右下角。当前位置正方形边长最大取决于，上，左上，和左为有下点边长最小的。f[i][j] 表示以i和j作为正方形右下角可以拓展的最大边长。状态转换式为：f[i][j] = min(f[i - 1][j], f[i][j-1], f[i-1][j-1]) + 1。

这道题空间可以优化，用滚动数组在实现。行变为滚动数组。

九章上面的答案比较复杂，leetcode article 官方答案更简洁。把dp矩阵多留一行和一列，就不用考虑初始化dp[0][j]和dp[i][0]的问题了。https://leetcode.com/articles/maximal-square/#approach-3-better-dynamic-programming-accepted

 public class Solution {  
   public int maximalSquare(char[][] matrix) {  
     int rows = matrix.length, cols = rows > 0 ? matrix[0].length : 0;  
     int[][] dp = new int[rows + 1][cols + 1];  
     int maxsqlen = 0;  
     for (int i = 1; i <= rows; i++) {  
       for (int j = 1; j <= cols; j++) {  
         if (matrix[i-1][j-1] == '1'){  
           dp[i][j] = Math.min(Math.min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]) + 1;  
           maxsqlen = Math.max(maxsqlen, dp[i][j]);  
         }  
       }  
     }  
     return maxsqlen * maxsqlen;  
   }  
 }  

下面的代码是空间优化后的：

 public class Solution {  
   public int maximalSquare(char[][] matrix) {  
     int rows = matrix.length, cols = rows > 0 ? matrix[0].length : 0;  
     int[] dp = new int[cols + 1];  
     int maxsqlen = 0, prev = 0;  
     for (int i = 1; i <= rows; i++) {  
       for (int j = 1; j <= cols; j++) {  
         int temp = dp[j];  
         if (matrix[i - 1][j - 1] == '1') {  
           dp[j] = Math.min(Math.min(dp[j - 1], prev), dp[j]) + 1;  
           maxsqlen = Math.max(maxsqlen, dp[j]);  
         } else {  
           dp[j] = 0;  
         }  
         prev = temp;  
       }  
     }  
     return maxsqlen * maxsqlen;  
   }  
 }  

因为dp[i][j]的状态只和当前第i行还有i-1行有关。dp[j-1]在左，pre对角，dp[j]在上（上一轮行为i-1的时候的dp[j]）。如果j+1, 那么上一轮的dp[j]就变成对角了，所以需要保存为prev。取出来没有更新的dp[j]其实是上一行的dp[j]。