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到一点点动态规划了，人生第一个动态规划的代码！
虽然有很多需要被优化的地方，但是好开心啊~

[NormanCarrie]

哇塞，代价函数耶

[XinJingHao]

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

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

[krahets]

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

[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]

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

[NormanCarrie]

其实不饶吧，你想一下，爬楼梯问题，实际上需要从一维数组可以变为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

[krahets]

Hi，可以发一下代码运行的结果吗，看看是否有误

[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