qilingit
diff --git a/‎May-LeetCoding-Challenge/21-Count-Square-Submatrices-With-All-Ones/Count-Square-Submatrices-With-All-Ones.java
Copy file name to clipboardExpand all lines: May-LeetCoding-Challenge/21-Count-Square-Submatrices-With-All-Ones/Count-Square-Submatrices-With-All-Ones.java
+37Lines changed: 37 additions & 0 deletions b/‎May-LeetCoding-Challenge/21-Count-Square-Submatrices-With-All-Ones/Count-Square-Submatrices-With-All-Ones.java
Copy file name to clipboardExpand all lines: May-LeetCoding-Challenge/21-Count-Square-Submatrices-With-All-Ones/Count-Square-Submatrices-With-All-Ones.java
+37Lines changed: 37 additions & 0 deletions
@@ -24,4 +24,41 @@ private boolean isSquare(int[][] square, int xfrom, int xto, int yfrom, int yto)
         }
         return true;
     }    
+}
+
+/**
+ * Dynamique programmingsolution
+ * Runtime: 5 ms
+ * Memory Usage: 49 MB
+ * Time complexity: O(m*n)
+ * Space complexity: O(1)
+ */
+class Solution2 {
+    public int countSquares(int[][] matrix) {
+        int length = matrix.length;
+        if (length == 0)    return 0;
+        
+        int width = matrix[0].length;
+        int res = 0;
+        
+        for (int i = 0; i < length; i++) {
+            for (int j = 0; j < width; j++) {
+                if (matrix[i][j] == 0)   continue;
+                
+                // border
+                if (i == 0 || j == 0) {
+                    res++;
+                    continue;
+                }
+                
+                // calculate min of different corner, and then plus himself
+                int min = Math.min(matrix[i-1][j-1], Math.min(matrix[i-1][j], matrix[i][j-1]));
+                matrix[i][j] += min;
+
+                res += matrix[i][j];
+            }
+        }
+        
+        return res;
+    }
 }