6/24, 动态规划，矩阵路径，滚动数组
潜水归来。刷起吧。
待刷类别: 记忆化搜索DP，博弈类DP，区间类DP，背包类DP，划分类DP
Unique Paths II
挺经典的 2D-array 上做 DP 问题。
public class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length; int n = obstacleGrid[0].length;
int[][] dp =new int[m][n];
dp[0][0]=obstacleGrid[0][0]==1?0:1;
for(int i=1;i<m;i++) //key point: start from 1
dp[i][0] = obstacleGrid[i][0]==1?0:dp[i-1][0];
for(int i=1;i<n;i++)
dp[0][i] = obstacleGrid[0][i]==1?0:dp[0][i-1];
for(int i=1;i<m;i++)
for(int j=1;j<n;j++){
if(obstacleGrid[i][j]==0) dp[i][j] = dp[i-1][j] + dp[i][j-1];
else dp[i][j] = 0;
}
return dp[m-1][n-1];
}
}
这个可以只建一纬。当前列中第j个一定是来自于d[j] (右边) 或者 d[j-1] (左边)
public class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
if (obstacleGrid == null || obstacleGrid.length == 0) return 0;
int m = obstacleGrid.length, n = obstacleGrid[0].length;
int[] dp = new int[n + 1];
dp[1] = 1;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (obstacleGrid[i - 1][j - 1] == 1) dp[j] = 0;
else dp[j] = dp[j] + dp[j - 1];
}
}
return dp[n];
}
}
Minimum Path Sum
思路一样，都属于 2D-array 上的路径问题。考虑到没有负数，也不存在往回走的情况，因此这个问题的 optimal substructure 比较简单，只依赖于来路的两个位置。
注意第一行第一列要特殊处理。
public class Solution {
public int minPathSum(int[][] grid) {
int rows = grid.length;
int cols = grid[0].length;
for(int i = 1; i < cols; i++){
grid[0][i] += grid[0][i - 1];
}
for(int i = 1; i < rows; i++){
grid[i][0] += grid[i - 1][0];
}
for(int i = 1; i < rows; i ++){
for(int j = 1; j < cols; j++){
grid[i][j] = Math.min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j];
}
}
return grid[rows - 1][cols - 1];
}
}
Maximal Square
两个注意
第一行第一列边界值是由自己的值确定的。可以调用Character.getNumericValue
matrix[i][j]=1时，此时构成的最大边长由三个小正方形最小边长决定。dp[i][j] = Math.min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j])+1
public class Solution {
public int maximalSquare(char[][] matrix) {
if(matrix == null || matrix.length==0 || matrix[0].length ==0)
return 0;
int m = matrix.length;
int n = matrix[0].length;
int[][] dp = new int[m][n];
for(int i=0;i<m;i++)
dp[i][0] = Character.getNumericValue(matrix[i][0]);
for(int j=0;j<n;j++)
dp[0][j] = Character.getNumericValue(matrix[0][j]);
for(int i=1;i<m;i++)
for(int j=1;j<n;j++){
if(matrix[i][j] == '1'){
int min = Math.min(dp[i-1][j], dp[i][j-1]);
min = Math.min(min, dp[i-1][j-1]);
dp[i][j] = min + 1;
}else{
dp[i][j] = 0;
}
}
int max = 0;
for(int i=0;i<m;i++)
for(int j=0;j<n;j++){
if(dp[i][j]>max)
max = dp[i][j];
}
return max*max;
}
}
因此，以(i,j) 为右下角的最大正方形边长，取决于以上三个点。Optimal substructure 确定。
剩下的优化就是滚动数组了，我们只需要保存前面一行以及当前行的左面，因此 int[2][cols].
循环初始化的细节要注意下，此外还要注意取mod的时候 % 是在最后，而不是(i % 2) - 1
public class Solution {
public int maximalSquare(char[][] matrix) {
if(matrix == null || matrix.length == 0) return 0;
int rows = matrix.length;
int cols = matrix[0].length;
int max = 0;
int[][] dp = new int[2][cols];
for(int i = 0; i < cols; i++){
dp[0][i] = matrix[0][i] - '0';
max = Math.max(dp[0][i], max);
}
for(int i = 1; i < rows; i++){
dp[i % 2][0] = matrix[i][0] - '0';
for(int j = 1; j < cols; j++){
if(matrix[i][j] == '0'){
dp[i % 2][j] = 0;
} else {
dp[i % 2][j] = Math.min(dp[i % 2][j - 1],
Math.min(dp[(i - 1) % 2][j],
dp[(i - 1) % 2][j - 1])) + 1;
}
max = Math.max(dp[i % 2][j], max);
}
}
return max * max;
}
}
Maximal Square Follow Up
01矩阵里面寻找一个对角线为 1， 其他全为 0 的矩阵
这题 LintCode 上还没有，所以就自己开 IDE 写，自己测 test case 了。思路和上一题类似。
由于连续对角线构造的依然是正方形，我们可以以一样的状态定义和转移方程来定义 (i,j) = 以 (i, j) 为起点的最大 1 对角线正方形。
对于(i , j)，我们可以通过(i - 1, j - 1) 来判断在对角线方向可以延伸多长；然而同时也要保证在 (i, j) 左面的宽为1的矩形全部是 0，上面宽为1的矩形也全部是0，其长度至少要等于 (i - 1, j - 1) 上的对角线长度。如果条件都满足，则可以继续 extend.
因此从 optimal substructure 来讲，和 Maximal Square 非常相似，都是从【左】【上】【对角线】来寻找能 valid 延伸的最长距离，其中最短的那个作为当前位置的 bottleneck.
我们需要构造额外的两个 DP 矩阵，用于记录对于每个位置 (i, j) 能向上和向左延伸的最长连续 0 长度。 O(mn) 时间， O(mn) 空间。
leftLen 和 upLen 也可以用滚动数组优化，不过貌似只能优化其中一个。
public class Main {
private static int maximalDiagnoal(int[][] matrix){
if(matrix == null || matrix.length == 0) return 0;
int rows = matrix.length;
int cols = matrix[0].length;
int[][] leftLen = new int[rows][cols];
int[][] upLen = new int[rows][cols];
int max = 0;
for(int i = 0; i < cols; i++){
if(matrix[0][i] == 0) upLen[0][i] = 1;
max = Math.max(max, matrix[0][i]);
}
for(int i = 0; i < rows; i++){
if(matrix[i][0] == 0) leftLen[i][0] = 1;
max = Math.max(max, matrix[i][0]);
}
for(int i = 1; i < rows; i++){
for(int j = 1; j < cols; j++){
if(matrix[i][j] == 0){
leftLen[i][j] = leftLen[i][j-1] + 1;
upLen[i][j] = upLen[i-1][j] + 1;
}
max = Math.max(max, matrix[i][j]);
// By default 0
}
}
int[][] dp = new int[2][cols];
for(int i = 0; i < cols; i++){
dp[0][i] = matrix[0][i];
}
for(int i = 1; i < rows; i++){
dp[i % 2][0] = matrix[i][0];
for(int j = 1; j < cols; j++){
if(matrix[i][j] == 1){
int diag = dp[(i-1) % 2][j-1];
int left = leftLen[i][j-1];
int up = upLen[i-1][j];
int min = Math.min(diag, Math.min(left, up));
dp[i % 2][j] = min + 1;
if(min + 1 > max){
max = min + 1;
System.out.println("Row : " + i + " Col : " + j);
System.out.println("Current Max : " + (min + 1));
}
}
}
}
return max;
}
public static void main(String[] args){
int[][] matrix1 = {{0,1,1,0,0,1},
{1,0,0,1,0,1},
{0,1,1,0,0,1},
{1,1,0,1,0,1},
{1,0,0,0,1,0}};
int[][] matrix2 = {{1,0,0,0,0,1},
{0,1,0,0,0,1},
{0,0,1,0,0,1},
{0,0,0,1,0,1},
{0,0,0,0,1,0}};
int[][] matrix3 = {{1,0,0,0,0,1},
{0,1,0,0,0,1},
{0,0,1,0,0,1},
{0,0,0,1,0,1},
{0,0,1,0,1,0}};
testRun(matrix1);
testRun(matrix2);
testRun(matrix3);
}
private static void testRun(int[][] matrix){
for(int i = 0; i < matrix.length; i++){
for(int j = 0; j < matrix[0].length; j++){
System.out.print(matrix[i][j] + " ");
}
System.out.println();
}
System.out.println("Max square with 1's only at diagnal : " + maximalDiagnoal(matrix));
}
}
Maximal Rectangle
这题显然就比 Maximal Square 复杂了，因为只有一个边长无法确定矩形位置，更无法确定面积。因为多了一个变量，所以我们的 DP 要多加一个维度，dp[i][j][k] = 以(i, j) 为右下角，底边长度为 k 的最大矩形高度。时间复杂度为 O(n^3)
我不太建议也不太觉得面试会考这种三维的 DP... 这题其实更适合用 maximal histogram 的思路去做，等我之后再回来搞定这题。
public class Solution {
public int maximalRectangle(char[][] matrix) {
if(matrix==null || matrix.length==0 || matrix[0].length==0) return 0;
int m = matrix.length; int n = matrix[0].length;
int[] heights = new int[n];
int[] left = new int[n]; Arrays.fill(left, -1);
int[] right = new int[n]; Arrays.fill(right, n);
int globalMax = 0;
for(int i=0;i<m;i++){
int curleft = -1; int curright= n;
for(int j=0;j<n;j++){
if(matrix[i][j]=='1') heights[j]++;
else heights[j]=0;
}
for(int j=0;j<n;j++){
if(matrix[i][j]=='1') left[j] = Math.max(left[j], curleft);
else{
left[j] = -1; curleft=j;
}
}
for(int j=n-1;j>=0;j--){
if(matrix[i][j]=='1') right[j] = Math.min(right[j], curright);
else{
right[j] = n; curright=j;
}
}
for(int j=0;j<n;j++){
int localMax = (right[j]-left[j]-1)*heights[j];
globalMax = Math.max(localMax, globalMax);
}
}
return globalMax;
}
}
public class Solution {
public int maximalRectangle(char[][] matrix) {
if(matrix==null || matrix.length==0 || matrix[0].length==0) return 0;
int m = matrix.length; int n = matrix[0].length;
int[] heights = new int[n];
int globalMax = 0;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(matrix[i][j]=='1') heights[j]++;
else heights[j]=0;
}
int localMax = largestRectangleArea(heights);
globalMax = Math.max(globalMax, localMax);
}
return globalMax;
}
public int largestRectangleArea(int[] heights) {
int[] left = new int[heights.length];
int[] right = new int[heights.length];
Stack<Integer> rstack = new Stack<Integer>();
for(int i=0;i<heights.length;i++){
while(!rstack.isEmpty() && heights[rstack.peek()]>heights[i])
right[rstack.pop()] = i;
rstack.push(i);
}
while(!rstack.isEmpty()) right[rstack.pop()] = heights.length;
Stack<Integer> lstack = new Stack<Integer>();
for(int i=heights.length-1;i>=0;i--){
while(!lstack.isEmpty() && heights[lstack.peek()]>heights[i])
left[lstack.pop()] = i;
lstack.push(i);
}
while(!lstack.isEmpty()) left[lstack.pop()] = -1;
int maxArea = 0;
for(int i=0;i<heights.length;i++){
maxArea = Math.max(maxArea, (right[i]-left[i]-1) * heights[i]);
}
return maxArea;
}
}