DP with Matrix

How to view a matrix ?

1. ROW by ROW, COL by COL.
2. ending at a position with some edge length.(longest '1').

Some base question

• Longest consequective '1'.
• Largest subarray sum.

Classical DP Questions

Maximal Square

My Solution 1 :

1. How to represent a square ?
   • . a point
   • top edge length
   • left edge length
2. How to get a 'square' area given a point ?
   • Math.min(X.toUp, X.toLeft) ^ 2
3. Result : among all possible square area for each point in matrix.

4. Time: O(mn) two pass

   Space: O(mn)

Optimized DP

We only care about minimum to its up and to its left.

a square is like

         x3  x1
         x2  x

if M[i][j] represents a matrix with length M[i][j] where rightBottom lies at (i,j).

if M[i][j] = Min(x1,x2,x3) + 1 (if current is 1).

else M[i][j] = 0.

Space Optimized DP

M[i][j] = Math.min(M[i - 1][j], M[i][j - 1], M[i - 1][j - 1]) + 1; = 0;

we only need two rows / cols. Rolling Array

public int minSquare (int[][] matrix) {
    if (matrix.length == 0 || matrix[0].length == 0) {
        return 0;
    }
    int[][] M = new int[2][matrix[0].length + 1];
    int globalMax = 0;
    for (int i = 1; i <= matrix.length; i++) {
        for(int j = 1; j <= matrix[0].length; j++) {
            if (matrix[i - 1][j - 1] == 1) {
              int n = Math.min(Math.min(M[(i - 1)% 2][j], M[i % 2][j - 1]), M[(i - 1) % 2][j - 1]) + 1;
              M[i % 2][j] = n;
              globalMax = Math.max(globalMax, n * n);
            } else {
               M[i % 2][j] = 0;
            }
        }
        return globalMax;
    }
}

Android unlock patterns

Step 1 : Clarify Questions, make sure you understand the question clearly.

Step 2: