关于recursion和DP的一点儿小心得

Mark下在看

mark！！！楼主大好人

谢谢分享，我一旦遇到tree recursion就懵逼。。。。真的是要把步骤想透彻，不然当时看着答案写出来了，遇倒新题又懵了。。

马克一下！

谢谢楼主分享。

DP的话，其实我自己感觉就是几个要点
1) 大问题的解，能够通过小问题的解，非常容易地得到，也就是所谓的最优子结构

2) 解大问题的时候，遇到很多非常像的小问题，就可以只算一次小问题，然后存起来，下一次再用到这个小问题的解，直接拿出来用，不用再算一次，节省很多时间（特别是子问题的解也很消耗计算能力的时候），也就是所谓的重叠子问题

3) 确定 dp 的语义，比如楼主提到的那道题的 dp[i][j] 的 语义就是 “从原点 [0][0] 出发，到 [i][j] 这个格子的最短距离是多少”

4) 确定状态转移方程，就是大问题，怎么通过小问题的解来得到，还是拿楼主提到的这道题来说，确定 dp 语义之后，再考虑题目的限制只能往下走或者往右走，那么就清楚了 dp[i][j] = min( dp[i][j - 1], dp[i - 1][j] ) + matrix[i][j]， 再确定好边界条件，都可以直接在脑子里面看到代码了，直接上屏就可以

谢谢楼主的分享，很实用，谢谢

请叫我热情老八 发表于 2019-8-3 00:43
谢谢楼主分享。

DP的话，其实我自己感觉就是几个要点

非常有用的信息。 但有一个问题我想确定一下，
如果不限制“只能往下走或者往右走”， 就是说 可以往 四个方向走，那么状态转移方程好像还是不变的。不知道对不对。

ucsd_cs_Grad 发表于 2019-11-29 02:06
非常有用的信息。 但有一个问题我想确定一下，
如果不限制“只能往下走或者往右走”， 就是说 可以往 四 ...

不对。如果走的方向不限制就不能用动态规划来做了，它变成了一个最短路问题。

波风水门 发表于 2019-11-29 03:52
不对。如果走的方向不限制就不能用动态规划来做了，它变成了一个最短路问题。

我是这样理解的。
dp[m][n] = min( dp[m-1][n], dp[m][n-1]) + grid[m][n]

这里我理解  dp[m-1][n]  子问题 是 给定 grid (m-1) X (n) 求 原点（0，0） 到 [m-1][n] (左上角到右下角)的最短数字和路径。
dp[m][n - 1]  子问题 是 给定 grid (m) X (n - 1) 求 原点（0，0） 到 [m][n - 1](左上角到右下角) 的最短数字和路径。

值得注意的是，我这里的子问题的条件当中，grid的size也随之变化了。因为原问题是 给定 mXn， 求远点到右下角。

不知道我这种在子问题当中把 grid size也变了，这样思路可以不可以呢？
然后这样的话，随意任意的子问题，因为是右下角，所以只需要考虑上边和左边。所以就得出了 即便move的方向是四个方向的，仍然只需要考虑上面和左边，因为子问题的目的地 只会在右下角。

ucsd_cs_Grad 发表于 2019-11-29 04:41
我是这样理解的。
dp[m][n] = min( dp[m-1][n], dp[m][n-1]) + grid[m][n]

想一想这个例子

0 0 0 0 0
1 1 1 1 0
0 0 0 0 0
0 1 1 1 1
0 0 0 0 0

你的动态规划能正确返回 0 吗？