2/5 array DP & 滚动数组
House Robber
Minimum Path Sum
坐标型
分析：
for the first row, we only move from left to right, while for the first column, we can only move from top to down,.
for the other cell, we should compare left cell, upper cell and choose the minimum sum of the path.
state: f[x][y] 代表从起点走到(x,y)的最短路径
function: f[x][y] = min(f[x-1][y], f[x][y-1]) + grid[x][y]
initialize: f[i][0] = sum(0,0 ~ i,0), f[0][i] = sum(0,0 ~ 0,i)
answer: f[m-1][n-1]
class Solution {
public int minPathSum(int[][] grid) {
int row = grid.length;
int col = grid[0].length;
int[][] dp = new int[row][col];
dp[0][0] = grid[0][0];
// initialize the first row
for (int i = 1; i < grid[0].length; i++){
dp[0][i] = dp[0][i - 1] + grid[0][i];
}
// initialize the first column
for (int i = 1; i < grid.length; i++){
dp[i][0] = dp[i - 1][0] + grid[i][0];
}
for(int i = 1; i < row; i++){
for(int j = 1; j < col; j++){
dp[i][j] = Math.min(dp[i - 1][j],dp[i][j - 1]) + grid[i][j];
}
}
return dp[row - 1][col - 1];
}
}
初始化一个二维的动态规划时，就去初始化第0行和第0列。还有我们可以不去开辟一个全新的DP数组，直接吧结果存储在original matrix上面。
Unique Paths
- 坐标型
分析：
state: f[x][y] 代表从起点到(x,y)的路径数
function: f[x][y] = f[x-1][y] + f[x][y-1]
initialize: f[0][i] = 1, f[i][0] = 1
answer: f[m-1][n-1]
class Solution {
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
for (int i = 0; i < m; ++i) {
dp[i][0] = 1;
}
for (int i = 0; i < n; ++i) {
dp[0][i] = 1;
}
for (int i = 1; i < m; ++i) {
for (int j = 1; j < n; ++j) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
}
}
how to optimized space complexity for the above solution:
public int uniquePaths(int m, int n) {
int[] row = new int[n];
Arrays.fill(row,1);
for ( int i = 1; i < m; i++){
for ( int j = 1; j < n; j++){
row[j]+=row[j-1];
}
}
return row[n-1];
}
}
follow up: Unique Paths II
加了obstacle, 只是逻辑上需要事先判断下是否为1，为1我就set as 0，其他都一样。
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
if (obstacleGrid == null || obstacleGrid.length == 0) return 0;
int m = obstacleGrid.length;
int 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];
}
}
note: 为什么我初始化的时候要new int[n + 1]. 因为如果没有n + 1,
那么我DP赋值的时候需要判断下index的取值范围，以免越界，其实加不加1都是可以做的
感觉+1就是为了能够简化dp array的初始化，如果不可避免要初始化，那么就不加1
else dp[j] = dp[j] + dp[j - 1];
=>
else if (j > 0) dp[j] = dp[j] + dp[j - 1];
上一道题，没有加1，是因为它对第一列没有限制要求。
Maximal Square
首先看下BF怎么做，对每一个遇到的1，都extend diagonally (right and downward), check whether new-added row or column exist all 1. If it exists, then update the square nodes, and extend till it cannot form valid 'all 1' square.
class Solution {
public int maximalSquare(char[][] matrix) {
if (matrix == null || matrix.length == 0) return 0;
int m = matrix.length;
int n = matrix[0].length;
int max = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (matrix[i][j] == '1') {
int count = 1;
boolean found = false;
int row = i + 1, col = j + 1;
while (row < m && col < n && !found) {
for (int k = j; k <= col; ++k) {
if (matrix[row][k] == '0') {
found = true;
}
}
for (int k = i; k <= row; ++k) {
if (matrix[k][col] == '0') {
found = true;
}
}
if (!found) {
count += ((row - i + 1) * 2 - 1);
}
row++;
col++;
}
max = Math.max(max, count);
}
}
}
return max;
}
}
如果熟悉DP问题，可以发现这里存在有天然的overlap subproblems，因而重点在于states之间的关联和构造，寻找optimal substructure. 正方形在2D-array上的定位相对简单，只需要有一个顶点，加上边长就可以，其中对于所有正方形，顶点位置固定。既然矩阵DP大多从左上向右下扫，用正方形右下角定位比较简便。
对于每一个位置(i,j):
- 其边长向左扩展受限于(i, j-1);
- 其边长向上扩展受限于(i-1, j);
- 其边长向对角线扩展受限于(i-1, j-1);
因此，以(i,j)为右下角的最大正方形边长，取决于以上三个点。Optimal substructure确定。
dp[i][j] represent the length of edge in the square that can be formed based on the right bottom "1".
Starting from index(0, 0), for every 1 found in the original matrix, we update the value of the current element as
dp(i, j) = min(dp(i-1, j) , dp(i-1, j-1), dp(i, j-1)) + 1
We also remember the size of the largest square found so far. In this way, we traverse the original matrix once and find out the required maximum size.
eg. to understand how solution works, see the figure below:
An entry 2 at (1, 3)(1,3) implies that we have a square of side 2 up to that index, similarly, ... now, consider the case for the index (3, 4). ...
time complexity: O(mn) single pass
space complexity: O(mn) another matrix of same size is used for dp.
class Solution {
public int maximalSquare(char[][] matrix) {
if (matrix == null || matrix.length == 0) return 0;
int m = matrix.length;
int n = matrix[0].length;
int[][] dp = new int[m + 1][n + 1];
int max = 0;
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (matrix[i - 1][j - 1] == '1') {
int temp = Math.min(dp[i - 1][j - 1], dp[i][j - 1]);
dp[i][j] = Math.min(temp, dp[i - 1][j]) + 1;
max = Math.max(max, dp[i][j] * dp[i][j]);
}
}
}
return max;
}
}
剩下的优化就是滚动数组了，我们只需要保存前面一行以及当前行的左面，因此int[2][cols]. 如何表示当千行的左面，用一个2维数组，然后(i - 1) % 2.
class Solution {
public int maximalSquare(char[][] matrix) {
if (matrix == null || matrix.length == 0) return 0;
int m = matrix.length;
int n = matrix[0].length;
int[][] dp = new int[2][n + 1]; // note that: should store the previous row
int max = 0;
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (matrix[i - 1][j - 1] == '1') {
int temp = Math.min(dp[(i - 1)%2][j], dp[i%2][j - 1]);
dp[i%2][j] = Math.min(temp, dp[(i - 1)%2][j - 1]) + 1;
max = Math.max(max, dp[i%2][j] * dp[i%2][j]);
} else {
dp[i%2][j] = 0; // note that: we should set this cell as 0
}
}
}
return max;
}
}
maximal square 2
note that, beside the dp[i][j] representing the side length of the formed square whose right bottom cell is at the index i, j
we need another two matrix, upper, and left, upper[i][j] represent the .... left[i][j] represent the ....
so if cell's value is 1, we say upper[i][j] = 0 and left[i][j] = 0; dp[i][j] = min(upper[i-1][j], left[i][j-1], dp[i-1][j-1])
if cell's value is 0, we say upper[i][j] = upper[i - 1][j] + 1; left[i][j] = left[i][j - 1] + 1; dp[i][j] = 0;
public int maxSquare2(int[][] matrix) {
// write your code here
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 + 1][n + 1];
// the length of the upper long area that are all '0' and start from matrix[i][j]
int[][] upper = new int[m + 1][n + 1];
// the length of the left long area that are all '0' and start from matrix[i][j]
int[][] left = new int[m + 1][n + 1];
int maxArea = 0;
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (matrix[i - 1][j - 1] == 1) {
upper[i][j] = 0;
left[i][j] = 0;
int temp = Math.min(dp[i - 1][j - 1], upper[i - 1][j]);
dp[i][j] = Math.min(temp, left[i][j - 1]) + 1;
// System.out.println("the dpij is " + dp[i][j]);
maxArea = Math.max(maxArea, dp[i][j] * dp[i][j]);
}
else {
upper[i][j] = upper[i - 1][j] + 1;
left[i][j] = left[i][j - 1] + 1;
dp[i][j] = 0;
}
}
}
return maxArea;
}