chapter_dynamic_programming/dp_solution_pipeline/

[giscus[bot]]

chapter_dynamic_programming/dp_solution_pipeline/

动画图解、一键运行的数据结构与算法教程

https://www.hello-algo.com/chapter_dynamic_programming/dp_solution_pipeline/

[zhuasdfg]

for (int i = 1; i < n; i++) {
// 状态转移：首列
dp[0] = dp[0] + grid[i][0];
// 状态转移：其余列
for (int j = 1; j < m; j++) {
dp[j] = Math.min(dp[j - 1], dp[j]) + grid[i][j];
}
}这块好难，看不懂，k神能整个图吗

[krahets]

在逻辑上，状态压缩前后是一致的，因此上面的动画就展示了这段代码的过程。

唯一的区别是，由于我们只保留了一行，因此一开始就不能将“第一列”全部初始化了，只能在遍历过程中一个一个地初始化，对应这一句：

// 状态转移：首列
dp[0] = dp[0] + grid[i][0];

[WhiteRhinos]

 /**
     * 状态压缩
     * @param grid 权值表
     * @param ti 查询点的坐标
     * @param tj 查询点的坐标
     * @return 最有路径
     */
    public static int dp3(int[][] grid, int ti, int tj)
    {
        // dp表(假设在grid外围还有一圈权值为max,所以长度要在原先基础上+1)
        int[] record = new int[tj + 1 + 1];
        Arrays.fill(record, Integer.MAX_VALUE);

        for (int i = 0; i <= ti; i++)
        {
            for (int j = 0; j <= tj; j++)
            {
                // 状态转移(注意record[1]存储的是(i,0)的最优解,record[0]一直为max)
                record[j + 1] = i == 0 && j == 0 ? grid[i][j] : Math.min(record[j + 1], record[j]) + grid[i][j];
            }
        }

        
        return record[record.length - 1];
    }

[ellem2023]

dp[j] = min(dp[j - 1], dp[j]) + grid[i][j]; 这里 min里面的dp[j - 1]代表左边的格子，dp[j]是上一行赋值的，代表上面的格子。

[likz1994]

太厉害了！！！！！，义父，请受孩儿一拜

[krahets]

duck bubi !

[Rh0-aias]

总结：
暴力搜索：由于每步只能向下或者向右走，遍历所有可能到dp[i][j]的路径即可找出最小路径。
记忆搜索：记下暴力搜索中的中间结果用以剪枝，避免重复路径的计算。
动态规划：由于每步走法只有两种，最优解一定在两者比较之间产生。于是可以利用状态转移方程不断迭代求解。

一个小小疑惑：
在”第三步：确定边界条件和状态转移顺序“中，我不是很理解下面这个句子：
“处在首行的状态只能向右转移，首列状态只能向下转移，因此首行 i=0和首列 j=0是边界条件。”
在我看来，首行的状态是可以向下转移的，而首列的状态也是可以向右转移的。

如果我理解的没错的话，这里应该是指：
“处在首行的状态只能是由其左方也在首行的状态不断向右迭代而来，首列状态只能是由其上方也在首列的状态不断向下迭代而来，因此首行i=0和首列 j=0作为边界条件可以在求解前直接得出。”

[krahets]

是的，谢谢指出！原文有歧义，我优化一下这里的表述

[Ryan-BetterMe]

这个空间优化实在太妙了。

每一行的遍历开始的时候：dp[0] 是新一行的值，而dp[i] 是上一行的值，由此将其全部推导为当前行的值

[ForkauLeung]

图 14-16 的第2列貌似错了

[krahets]

哪里呢

[MrLiuWinter]

应该是max，图中用了min，问题不大

[MrLiuWinter]

看错了，不好意思

[Mingquan-cloud]

请教！DP问题如果可以列出DP表，看起来就包含着问题的解，那我们实际解决问题的时候比较确定这是一题符合DP问题特点的题目时，是否可以直接考虑使用DP表直接写出最终答案，而不需要考虑暴力搜索等其他解？因为好像有时候反而不容易想到要如何暴力搜索，而是很强烈的感觉这题用dp表可以做。

[krahets]

是否可以直接考虑使用DP表直接写出最终答案，而不需要考虑暴力搜索等其他解。

完全可以，实际上熟练之后就是这么做的，直接考虑 DP 递推的解法。
暴力搜索（递归）的方法和分治有一点类似，都是从子问题分解的角度进行分析的，这种分析方式比较适合推导转移方程

[Mingquan-cloud]

感谢k神回答！

[jialangli]

您好，我问一下：for i in range(1, n):
for j in range(1, m):
dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j]
return dp[n - 1][m - 1]中的dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j]，为什么dp[i - 1][j])加了grid[i][j]，但是dp[i][j - 1]不用加grid[i][j]，它不应该是两个都需要加吗？

[jialangli]

4.空间优化dp[j] = min(dp[j - 1], dp[j]) + grid[i][j] 好像少了一个括号

[jialangli]

不好意思，这个看错了

[krahets]

Hi，+ grid[i][j] 操作是在 min() 之外的

[bluedarkni]

如果右上的5和2都换成1，这个每次选最小的，出来的路线就不不对了，这样直接走两条直角边总和才10

[bluedarkni]

就是0,3和1,3 这两个栅格的值都是1

[bluedarkni]

理解错了...

[lwd-coding]

文中的先观察问题是否适合使用回溯（穷举）解决这句话感觉可以调整成是否适合使用回溯（自上向下穷举）解决，因为我一开始用自下向上的回溯发现没法用记忆搜索优化，导致推导不出后面的问题，哈哈，可能是我太菜了

[krahets]

谢谢建议！一般来说从“子问题分解”的角度进行分析（从顶至底），比较容易进行记忆搜索优化～

[lwd-coding]

复杂的算法能从浅入深，作者的功力太强了，算法这种就是做出来容易讲出来让别人理解难

[Terran0629]

k神能省则省，这思路太牛了

[chnynf]

给大佬提一个可能不合理的小建议，如果在代码之前写一下输入和输出是什么，可能会更容易让凡人理解。

[krahets]

Hi，你是指完整带测试样例的代码吗？请前往仓库 https://github.com/krahets/hello-algo 下载代码，包含测试样例，可在本地运行

[chnynf]

我想说的标注一下比如：输入grid是长这样：[[1, 3, 1, 5], [2, 2, 4, 2], [5, 3, 2, 1], [4, 3, 5, 2]]，输出是长这样：13。不过我看到可视化运行里已经有了，只是没在正文。

[XinJingHao]

import torch

cost = torch.tensor([[1,3,1,5],
                     [2,2,4,2],
                     [5,3,2,1],
                     [4,3,5,2]])

dp = torch.ones_like(cost)*torch.inf
dp[0,0] = 1

for i in range(4):
    for j in range(4):
        last_i = i-1
        last_j = j-1

        if last_i>=0 and last_j>=0:
            dp[i,j] = torch.min(dp[last_i,j], dp[i,last_j]) + cost[i,j]
        elif last_i>=0 and last_j<0:
            dp[i, j] = dp[last_i, j] + cost[i, j]
        elif last_i<0 and last_j>=0:
            dp[i, j] = dp[i, last_j] + cost[i, j]
        else:
            pass

print(dp[3,3])

终于好像有get到一点点动态规划了，人生第一个动态规划的代码！
虽然有很多需要被优化的地方，但是好开心啊~

[ghost]

哇塞，代价函数耶

[XinJingHao]

感觉动态规划和强化学习好像啊。 强化学习里面也有初始状态、终止状态、马尔科夫性、状态转移方程。 或者是否能说DP和RL都是用来解决序列决策问题的方法，不过DP要求问题的状态转移方程已知；而RL则通过与环境互动学习各个状态的最优决策，不需要状态转移方程。

另外有一个问题，DP问题中，如何对状态转移进行剪枝呢？换句话说，如何对设计合适的状态转移方法，尽可能少地探索状态以到达我们的目标状态？

[krahets]

这个得看具体问题的性质～ 例如对于许多问题，贪心算法可以看作是动态规划的一种“剪枝”后的解法

[YiChau]

我也觉得和强化学习很像，哈哈哈。

[RENHJa]

Hi,我有些疑问。如果我有个4*4的表格

{ 
{1,1,0,1},
{1,3,1,1},
{1,1,1,1},
{0,0,0,0} };

如果我要求从左上角到（2，2）的最小路径和，根据这个算法得到的结果是4，没有问题。
那如果把（2，2）的值换成10呢？程序运行的结果会是13。显然13不是从左上角到（2，2）的最小路径和。

[krahets]

没问题的。到达 (2, 2) 时要加上该格子的值 10， 因此是 1 + 1 + 1 + 10 = 13

[lihuangshuaige]

回溯算法不是需要做出选择与回退选择吗，看代码里没有体现呢

[MeowLiu]

其实你也可以写成那样的形式，但是时间复杂度会更高很多

[lt421]

这小节的空间优化还是有点绕。很巧妙。

[ghost]

其实不饶吧，你想一下，爬楼梯问题，实际上需要从一维数组可以变为2个变量，因为他只关心前面和前面的前面，进一步你在思考下，你是怎么在里面走，是不是一层for循环就ok了，同样的道理，这个是两层循环，没一层循环是走一行哦。他是需要把上一行遍历的结论全部带到本行来的，因此需要一个一维数组来保证上一次迭代的结果。哎呀，我好笨，我怎么就想不到这么好的方法呢，卡哥哥也太牛逼了吧

[TapTapLucas]

需要思考清楚一点就是：目前为止提到的空间优化的案例，都是“无后效性”特性的体现。

可以多想想如何让每一个人都背负上前世的孽债，讨债的时候只找这一个人就行了~ （x不是

[Jinjin680]

// 若为左上角单元格，则终止搜索
if (i == 0 && j == 0) {
return grid[0][0];
}
为什么是返回grid[0][0]，而不是返回（到达上个格子的代价+grid[i][j])呀

[Jinjin680]

不好意思，把and看成or了

[Snow-02]

a=[[1,1,2,3],
   [10,1,0,0]
   [1,1,2,1]]

k神你好，对于其中dp[2,0]的值按照初始化为12，但是按照最小代价来看，不应该是1+1+1+1+1为5

[Snow-02]

from math import inf
grid = [[1, 1, 2, 3], [10, 1, 0, 0], [1, 1, 2, 1]]
n, m = len(grid), len(grid[0])
# 初始化 dp 表
dp = [[0] * m for _ in range(n)]
dp[0][0] = grid[0][0]
# 状态转移：首行
for j in range(1, m):
    dp[0][j] = dp[0][j - 1] + grid[0][j]
# 状态转移：首列
for i in range(1, n):
    dp[i][0] = dp[i - 1][0] + grid[i][0]
# 状态转移：其余行和列
for i in range(1, n):
    for j in range(1, m):
        dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j]
print(dp[2][0])

输出结果为12

[krahets]

请使用书中的原始代码测试，测试结果为：

grid = [[1, 1, 2, 3], [10, 1, 0, 0], [1, 1, 2, 1]]

从左上角到右下角的做小路径和为 4

[WesChiou]

兄台，这用瞪眼法都能看出是 1+1+1+0+0+1=4呀

[zhangben0408]

兄弟，为什么要print(dp[2][0])，按照题意，不应该print(dp[2][3])吗？

[Xinkun666]

只能向下和向右，不能向左

[duluaibuna]

怎么把最短路径索引也记录下来？

[linyubian]

先绘出dp图，然后从终点开始，减去当格代价，逆推路径并记录

[linyubian]

或者每格都记录上一格的位置

[linyubian]

如果这个图尺寸变大，路径方向可能还会包含向上或者向左，涉及到新代价值计算先后的问题，是不是就不适用动态规划了

[GoldenJin24]

1.如果能够向上向下向左向右走，那么可能会存在2x2的方格和为正数，程序就会一直在这个2x2的方格内徘徊给自己加分，这样不存在最大值。

[LiHuigui]

尝试用前一章节学的回溯代码来暴力解决这个问题: 除了返回最小路径和以外，同时返回所有最小路径和的路径。
我将本节课的grid中第一行第二个数字改为2，使得出现多条路径的和都是最小和的情况

grid = [[1, 2, 1, 5], [2, 2, 4, 2], [5, 3, 2, 1], [4, 3, 5, 2]]
row=len(grid)
col=len(grid[0])
def backtrack(#python
    state:int,
    path:list[list[int]],
    i,
    j,
    choices:list[int],
    grid:list[list[int]],
    result:list[int],
    path_result:list[list[list[int]]]
):
    #state表示当前位置的路径和，path用来记录当前路径，i,j是当前位置的坐标
    #choices=[0,1],0表示向下走，1表示向右走
    #result是长度为1的列表，用来保存最小的state，path_result用来保存最小state对应的path
    #row,col表示grid的总行数和总列数，row,col,grid都是是全局变量

    #解的判断:是否已经走到最右下角
    if i == row-1 and j == col-1: 
        #result为空，说明是第一条路径，无论如何都记录
        if not result:
            result.append(state)
            path_result.append(list(path))
        #只要state比当前的result的更小，结果就更新。
        elif result[0]>state:
            result[0]=state
            #因为新的state更小，此前保存的path都无效了，需要清空path_result
            path_result.clear()
            path_result.append(list(path))
        #如果是重复的最小路径和，只添加这一条path进来   
        elif result[0]==state:
            path_result.append(list(path))
        return

    for choice in choices:
        if choice == 0:#=0表示向下走            
            if i == row-1:#剪枝
                continue#已经到底，不往下走了            
            #更新状态
            i+=1
            state+=grid[i][j]
            path.append([i,j])
            
            backtrack(state,path,i,j,choices,grid,result,path_result) 
            #回撤
            state-=grid[i][j]
            path.pop()
            i-=1
             
        if choice == 1:#=1表示向右走
            if j == col-1:
                continue
            j+=1
            state+=grid[i][j]
            path.append([i,j])
            backtrack(state,path,i,j,choices,grid,result,path_result)
            state-=grid[i][j]
            path.pop()
            j-=1
            
def min_path_sum_backtrack(grid:list[list[int]]):
    state=grid[0][0]
    result=[]
    path=[[0,0]]
    path_result=[]
    backtrack(state,path,0,0,[0,1],grid,result,path_result)
    return result[0],path_result
sum,path_list=min_path_sum_backtrack(grid)
#打印结果
print(f'最小路径和:{sum}')
for i in range(len(path_list)):
    print(f'\n最小路径{i+1}：')
    print(path_list[i])

[Gu0Menak]

请教，空间优化后的代码的dp表容量是只有4吗，也就意味着程序运行结束后只有最后一行的最小路径和？

[pianfan]

对的，就是一行一行滚动推进的。最后只需要返回右下角那个格子的最小路径

[BingzhengXia]

这里面第一个的暴力搜索算法是属于回溯算法吗？

[Clemna10]

感觉更像是分治

[BingzhengXia]

dp[j] = min(dp[j - 1], dp[j]) + grid[i][j]; 空间优化，思考了一会才理解，min里面的dp[j-1]是当前位置左边的格子的值，dp[j]是刚刚计算的上一行的对应位置的的值，所以刚好对应左边和上边两个元素，计算之后dp[j]就被当前位置的值替代，用来进行下一次的计算，巧妙！

[3Ajfdjsdsk2]

   请教各位

在记忆化搜索中假如mem数组一开始全是-1，首先求解dp[i][j] ,i和j均很大，那么实际上这种解法就是暴力搜索，因为搜索是从顶至底的，所以if (mem[i][j] != -1) return mem[i][j] 并没有发挥作用

[kestrel00]

C++版本代码中使用「min(left, up) != INT_MAX」是必要的吗？up和left应该不能同时返回INT_MAX吧？

[YiChau]

LeetCode 最小路径和 传送门： https://leetcode.cn/problems/minimum-path-sum/description/