fucking-algorithm
fucking-algorithm copied to clipboard
labuladong
动态规划之最小路径和 :: labuladong的算法小抄
前文 动态规划的降维打击：状态压缩 说过降低 dp 数组的技巧，这里也是适用的，不过略微复杂些
本题状态压缩可以直接去掉第一维 （大佬状态压缩那一节讲的太透彻了，醍醐灌顶了属于是）
优化之前代码如下：
public int minPathSum2(int[][] grid) {
int[] dp = new int[grid[0].length];
dp[0] = grid[0][0];
for (int i = 0;i<grid.length;i++){
for (int j =0;j<dp.length;j++){
if (i==0 && j==0){
continue;
}
if (i-1==-1){
dp[j] = dp[j-1]+grid[i][j];
continue;
}else if (j-1==-1){
dp[j] = dp[j]+grid[i][j];
continue;
}
dp[j] = Math.min(dp[j],dp[j-1])+grid[i][j];
}
}
return dp[dp.length-1];
}
状态压缩之后如下：
public int minPathSum2(int[][] grid) {
int[] dp = new int[grid[0].length];
dp[0] = grid[0][0];
for (int i = 0;i<grid.length;i++){
for (int j =0;j<dp.length;j++){
if (i==0 && j==0){
continue;
}
if (i-1==-1){
dp[j] = dp[j-1]+grid[i][j];
continue;
}else if (j-1==-1){
dp[j] = dp[j]+grid[i][j];
continue;
}
dp[j] = Math.min(dp[j],dp[j-1])+grid[i][j];
}
}
return dp[dp.length-1];
}
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int row = grid.size(), col = grid[0].size();
vector<int> dp(col);
dp[0] = grid[0][0];
for(int j = 1; j<col; ++j) dp[j] = dp[j-1] + grid[0][j];
for(int i = 1; i<row; ++i){
dp[0] = grid[i][0] + dp[0];
for(int j = 1; j<col; ++j){
dp[j] = grid[i][j] + min(dp[j], dp[j-1]);
}
}
return dp[col-1];
}
};
也可以用Dijkstra算法求解：
from queue import PriorityQueue
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
sol = [ [0] * len(grid[0]) for _ in grid ]
visited = set()
queue = PriorityQueue()
queue.put( (grid[0][0], (0, 0)) )
sol[0][0] = grid[0][0]
while not queue.empty():
val, node = queue.get()
if node in visited:
continue
visited.add(node)
sol[node[0]][node[1]] = val
if node[0]+1<len(grid):
down = (node[0]+1, node[1])
queue.put( (grid[down[0]][down[1]] + val, down) )
if node[1]+1<len(grid[0]):
right = (node[0], node[1]+1)
queue.put( ( grid[right[0]][right[1]] + val, right) )
return sol[-1][-1]
这是第一道靠自己的能力写出来的，多亏了东哥之前的解决，从之前的一道也看不懂，到后来的看了半天才能看懂，再到今天第一次自己写出来。感觉算法确实很难，但是也能从中获得乐趣。
有一个问题是，东哥后面的好多题目都是通过dptable写出来的，当我自己尝试通过dp函数写的时候，我发现我无法写出，dptable好像比dp函数要容易一些。也可能是我自己的功夫不到家，希望东哥可以多用dp函数解答题目。
Math.min( dp(grid, i - 1, j)+ grid[i][j], dp(grid, i, j - 1)+ grid[i][j] ) ; 这个为什么会报错的？感觉这个不是和 Math.min( dp(grid, i - 1, j), dp(grid, i, j - 1) ) + grid[i][j]; 等价吗？
@Yjppj 评论之前可以预览，想清楚再评论。你提出的这两种写法，现在看是等价的，但如果放到 for 循环里面，不见得相同，要根据具体情况来看。
python版 DPtable 状态压缩
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
m,n=len(grid),len(grid[0])
dp=[-1 for j in range(n)]
# base case 相当于dp[0][j]=sum(grid[0][0...j-1])
dp[0]=grid[0][0]
for j in range(1,n):
dp[j]=dp[j-1]+grid[0][j]
for i in range(1,m):
# base case 相当于dp[i][0]=sum(grid[0...i-1][0])
dp[0]+=grid[i][0]
for j in range(1,n):
dp[j]=min(dp[j],dp[j-1])+grid[i][j]
return dp[n-1]
原二维：
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
m,n=len(grid),len(grid[0])
dp=[[-1 for j in range(n)] for i in range(m)]
dp[0][0]=grid[0][0]
for j in range(1,n):
dp[0][j]=dp[0][j-1]+grid[0][j]
for i in range(1,m):
dp[i][0]=dp[i-1][0]+grid[i][0]
for i in range(1,m):
for j in range(1,n):
dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j]
return dp[m-1][n-1]
状态压缩思路
每次只存上一行的dp值
Code
C++
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
vector<int> dp(n,0);
dp[0] = grid[0][0];
for(int i=1; i<n; i++)dp[i] = dp[i-1] + grid[0][i];
for(int i=1; i<m; i++){
dp[0] = dp[0] + grid[i][0];
for(int j=1; j<n; j++){
dp[j] = grid[i][j] + min(dp[j], dp[j-1]);
}
}
return dp[n-1];
}
};
JavaScript
/**
* @param {number[][]} grid
* @return {number}
*/
var minPathSum = function (grid) {
let dp = new Array(grid[0].length);
dp[0] = grid[0][0];
for (let i = 1; i < dp.length; i++) {
dp[i] = dp[i - 1] + grid[0][i];
}
for (let row = 1; row < grid.length; row++) {
dp[0] += grid[row][0];
for (let j = 1; j < grid[0].length; j++) {
dp[j] = grid[row][j] + Math.min(dp[j - 1], dp[j]);
}
}
return dp[dp.length - 1];
};
因为备忘录和 grid 是一样大的，且由于前进方向是向右、向下，和我们的默认遍历方向一致，所以感觉可以 原地修改，直接把 grid 当成 备忘录来使用
public int minPathSum(int[][] grid) {
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[i].length; j++) {
int curVal = grid[i][j];
if (i == 0 && j == 0) {
grid[i][j] = curVal;
} else if(i == 0) {
// 左边+当前
grid[i][j] = grid[i][j-1] + curVal;
} else if(j == 0) {
// 上面+当前
grid[i][j] = grid[i-1][j] + curVal;
} else {
grid[i][j] = Math.min(grid[i][j-1], grid[i-1][j]) + curVal;
}
}
}
return grid[grid.length-1][grid[0].length-1];
}
空间复杂度，因为只使用了三个变量，为 O(1)
Java版本 压缩空间写法 Dijkstra 算法也可以写这题。算法真的太厉害啦。
/* 迭代压缩空间写法 */
public int minPathSum(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int[] dp = new int[n];
Arrays.fill(dp, Integer.MAX_VALUE);
// base case
dp[0] = grid[0][0];
// dp
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
// 第一行第一列。跳过，因为在base case 已经赋值
if (i == 0 && j == 0) continue;
// 非第一行的第一列，都只能从上面走到当前位置
if (j == 0) {
dp[j] = dp[j] + grid[i][j];
}else {
// 非第一行非第一列，可以从上面或者左边走到当前位置，取最小值
dp[j] = Math.min(dp[j - 1], dp[j]) + grid[i][j];
}
}
}
return dp[n - 1];
}
不知道为啥， 感觉降维这块 对于我来说老费劲了，搞了好几次，还是差点意思，哈哈哈哈。但是那篇降维文章还是很好的， 只是我对于新知识掌握的比较慢，大家加油！
我也试着压缩了一下,没想到过了哎
class Solution {
public int minPathSum(int[][] grid) {
//dp[i][j]可以由dp[i][j-1]和dp[i-1][j]而来
//那当然是要取上述二者中较小的一个:dp[i][j] = min(dp[i-1][j],dp[i][j-1])
int m = grid.length;
int n = grid[0].length;
int[] dp = new int[n];//因为想返回dp[m-1][n-1],索引哦
//应当注意边界问题,如:i==0则没有i-1,如:j==0则没有j-1
dp[0] = grid[0][0];
//因为第一行只能向右走
for(int i = 1;i<n;i++){
dp[i] = dp[i-1]+grid[0][i];
}
for(int i = 1;i<m;i++){
//因为第一行都已经被正确初始化了,所以i在递推公式中已经不会越界了
for(int j = 0;j<n;j++){
if(j==0){
dp[j] = dp[j]+grid[i][j];
}else{
dp[j]=Math.min(dp[j],dp[j-1])+grid[i][j];
}
}
}
return dp[n-1];
}
}
补充一个针对本题解法，也用到了空间压缩，当行数量小于列数量，定义一个长度等于行数量的数组横向滚动填表；当行数量大于列数量时，定义一个长度等于列数量的数组纵向填表
我这里dp定义为[x, y]坐标到右下角的最小值
class Solution {
public int minPathSum(int[][] grid) {
lastRow = grid.length - 1;
lastColumn = grid[0].length - 1;
if (lastRow < lastColumn) {
return dp1(grid, 0);
}
return dp2(grid, 0);
}
int lastRow;
int lastColumn;
// 行短
public int dp1(int[][] grid, int y) {
int[] dp = new int[lastRow + 1];
int[] last = grid[lastRow];
dp[lastRow] = last[lastColumn];
// 初始化
for (int i = lastRow - 1; i >= 0; i--) {
dp[i] = dp[i + 1] + grid[i][lastColumn];
}
for (int i = lastColumn - 1; i >= 0; i--) {
for (int j = lastRow; j >= 0; j--) {
if (j == lastRow) {
dp[j] = dp[j] + grid[j][i];
continue;
}
dp[j] = Math.min(dp[j], dp[j + 1]) + grid[j][i];
}
}
return dp[y];
}
// 列短
public int dp2(int[][] grid, int y) {
int[] dp = new int[lastColumn + 1];
int[] last = grid[lastRow];
dp[lastColumn] = last[lastColumn];
// 初始化
for (int i = lastColumn - 1; i >= 0; i--) {
dp[i] = grid[lastRow][i] + dp[i + 1];
}
for (int i = lastRow - 1; i >= 0; i--) {
for (int j = lastColumn; j >= 0; j--) {
if (j == lastColumn) {
dp[j] = dp[j] + grid[i][j];
continue;
}
dp[j] = Math.min(dp[j], dp[j + 1]) + grid[i][j];
}
}
return dp[y];
}
}
东哥，请问对于找工作跳槽而言，写题目时如动态规划，用递归还是迭代去解题好一点？两个的思想都去学习并且每个题目都写出两个方式的解题代码，这样感觉工作量有点大，，，（感觉东哥讲题主要是在使用递归）
