We were discussing counting submatrices of same binary value of size k x k in an overall rectangular matrix.
Since there are lot of overlapping subproblems in our previous approach, we can do this with dynamic programming as well. For example, we can establish a recurrence based on the current element being same as the element above it, the element to its left and the element diagonally top left to it in which case it creates a square smallest composite submatrix of size 2 x 2. The dp table matches the position of each matrix element. When the criteria is met, we take the minimum of the corresponding dp table values and add 1 for the current position. We initialize the dp table with 1 for all elements that do not match the criteria because the smallest square matrix is of size 1 x 1. This automatically means for a unit row or unit column matrix, the count is merely one because that is the only square matrix possible. Since we repeat with this criteria for all positions iterating from the top left of the rectangular matrix to the bottom right, this parity check adds a row and column to considerations for matrices starting at those positions. we take the minimum count encountered for each of the three positions and add one if the parity check is satisfied. The significance of adding one is that we keep a tally of smaller submatrices formed at those positions and a bigger submatrix formed at the current position. When we are done with our iterations, we can create a frequency array for different values of the dp table. Then as we cumulate the frequencies one element to the left in the frequency array. Since the processing is the same for either binary value matching 0 or 1 as per the parameter passed in, we can build the frequency table for 0 or 1 simultaneously.
For example for size 1 we have 3 entries and for size 2 we have one entry so when we cumulate we represent 4 matrix starting positions as contributing to size 1 and 1 matrix cell as contributing to size 2. We represent all matrix and submatrix starting position as the top-left.
The recursion is written as
(A [i,j] == A [i-1, j] &&
A [i,j] == A [i, j-1] &&
A [i,j] == A [i-1, j-1] )
=> dp [i,j] = math.min (dp [i-1,j], dp [i,j-1], dp [i-1, j-1]) +1;
Since there are lot of overlapping subproblems in our previous approach, we can do this with dynamic programming as well. For example, we can establish a recurrence based on the current element being same as the element above it, the element to its left and the element diagonally top left to it in which case it creates a square smallest composite submatrix of size 2 x 2. The dp table matches the position of each matrix element. When the criteria is met, we take the minimum of the corresponding dp table values and add 1 for the current position. We initialize the dp table with 1 for all elements that do not match the criteria because the smallest square matrix is of size 1 x 1. This automatically means for a unit row or unit column matrix, the count is merely one because that is the only square matrix possible. Since we repeat with this criteria for all positions iterating from the top left of the rectangular matrix to the bottom right, this parity check adds a row and column to considerations for matrices starting at those positions. we take the minimum count encountered for each of the three positions and add one if the parity check is satisfied. The significance of adding one is that we keep a tally of smaller submatrices formed at those positions and a bigger submatrix formed at the current position. When we are done with our iterations, we can create a frequency array for different values of the dp table. Then as we cumulate the frequencies one element to the left in the frequency array. Since the processing is the same for either binary value matching 0 or 1 as per the parameter passed in, we can build the frequency table for 0 or 1 simultaneously.
For example for size 1 we have 3 entries and for size 2 we have one entry so when we cumulate we represent 4 matrix starting positions as contributing to size 1 and 1 matrix cell as contributing to size 2. We represent all matrix and submatrix starting position as the top-left.
The recursion is written as
(A [i,j] == A [i-1, j] &&
A [i,j] == A [i, j-1] &&
A [i,j] == A [i-1, j-1] )
=> dp [i,j] = math.min (dp [i-1,j], dp [i,j-1], dp [i-1, j-1]) +1;
Courtesy: geeksforgeeks
No comments:
Post a Comment