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

本人刷题和学数据结构算法已经有一段时间，从最初的Easy题目都啃不动，到现在的medium难度基本没太大问题，中间经历了很多痛苦的挣扎。尤其是很多牵扯到动态规划的题，做的非常难受。其实说白了无非就是一开始没有深刻理解到底什么是递归，什么是动态规划。
简单来说，动态规划就是把每次递归计算出的结果保存起来以便下次直接使用，而不用再重复去计算，从而大大降低时间复杂度。今天重温了一道可以说很具有代表性的动态规划题目。在这里和那些跟我一样水平比较烂的选手进行分享，希望能帮到大家。因为本人水平很低，所以写出来的东西对于同样苦手的人来说可能更好理解。
先来看题，链接在此： Minimum Path Sum
我们先来看遇到这种题，该如何思考。🤔
这道题，要找到从左上角到右下角的最短数字和路径。
首先，我们把grid画出来

1     3     1

1     5     1

4     2     1

如果不写代码，让你判断，是不是很简单？ 我们人脑是如何判断的？是不是从grid[0][0]开始，在右边和下边的cell里选出数字更小的那个？一直到我们到达grid[row - 1][col - 1]。
那么我们先考虑一下如何用递归解这道题。 递归无非两点：
1. 基本条件，用于跳出递归。
2. 递归调用，是参数朝着基本条件的方向变化。
我们看这道题，用一个从上到下，倒退的做法， 从终点往起点倒退。基本条件，可以设定为到达grid[0][0]，也就是矩阵起始点。 那么递归部分也就是从grid[row - 1][col - 1]开始，也就是终点。
这里我们需要考虑到四个情况：
（1） row == 0, 也就是到达了第一行，就只有一个水平方向可以行进了。
（2） col == 0， 也就是到达了第一列，就只有一个竖直方向可以行进了。
（3） row和col 都等于0， 说明到达了起点，递归结束，返回这个cell的数值。
（4）其余所有不满足（1）（2）（3）的情况，我们都用这个cell的值 + 它左边和上边的cell期中更小的那个的值。

到此思路也就出来了，写一个helper函数把grid和坐标传进去就好。

递归的做法已经搞定了，那么DP也就不难了，因为其实思路是完全一样的，只不过我们把每次的结果都保存在数组的每个cell里。然后数组最后那一格的结果自然就是答案了。
直接用grid数组就好，用一个二重循环遍历，按照上面的四个条件把每一个方格填满就好了。

具体代码和解析我直接发在LeetCode评论里：
代码+解析


如果对大家有用，贫农求一波大米。谢谢。


补充内容 (2019-7-30 01:23):
完全没想到两天点击就突破了1500。可能说到了很多同学的痛点，很高兴有帮到大家。日后如果再有值得分享的经验会再发帖出来，回馈地里。谢谢大家。

谢谢楼主的讲解 ~~ 楼主能不能分享一下从开始刷题 复习算法到现在取得比较大的进步中间花了多长时间呀？

我只要做到dp, dfs都感觉很挣扎 有的时候思路逻辑都有了 码也写出来 但是中间有bug就很难理解到底是哪一步不对 我习惯用visualizer来查看每一步具体跑了什么 但是一旦到recursion的题 感觉就是一个loop还没跑完就继续层层往里面剥开 留下一大堆的parent在外面 这样过了一段时间真的完全乱了 >_< 最后一看答案 有时候跟我写的就是差了几个字 或者一两行顺序不一样 但我自己看的时候完全不明白为什么那样不对 有的recursion题代码写的不长 但是一跑visualizer发现中间有600多步 看到100多步就已经不懂正在发生什么事了 天呐 … 而且经常写着写着就发生maximum recursion exceeded … 也不知道再坚持多久时间 / 多少题能稍微突破一下

谢谢楼主分享。

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]， 再确定好边界条件，都可以直接在脑子里面看到代码了，直接上屏就可以

mchen117 发表于 2019-7-28 05:05
谢谢楼主的讲解 ~~ 楼主能不能分享一下从开始刷题 复习算法到现在取得比较大的进步中间花了多长时间呀？

...

完全理解。确实我也经历过这段过程。其实就是不可避免的。其实看你说的情况，你现在的状态挺好的。有思路，有代码，只是有些小瑕疵，这些在OA以外的电话面试中，都是有价值的。毕竟人家考察的是你分析问题和灵活运用所学知识的能力，并不一定要100%把题目做对。我也喜欢用具体的可视化过程去模拟代码运行过程，对于我们这种还属于水平一般般的人非常合适。只不过就像你说的，有时候recursive的问题确实比较麻烦，也不太好debug，这种时候还是自己找张纸，把每次递归的分支都画出来，每次不同的参数都分出来。其实说白了递归调用画出来，就是tree，每次调用就是tree的一个节点。我自己的话，断断续续加起来也能有三四个月。现在也没有很熟练，依然是半吊子水平，只是现在感觉比一个月前对问题的认识和知识储备的运用能力上了个一个层次，起码看到一道题，大概有想法，这道题应该用什么数据结构和算法会比较合适。说到底还是不断练习不断熟悉吧。顺便说下DFS BFS，对我帮助最大的是看书了解Graph的两种遍历。其实套路是固定的，无非DFS用递归，BFS用Queue。然后自己封装个graph类，自己写一遍两种遍历方法。当然了，做任何题的时候，先在纸上画画写写，想想如果没有计算机，我会如何解决这道题？然后再转化为代码。记住，写代码一定是最后测试之外的最后一步。共勉。加油。

很清晰明了

钢铁侠吉米 发表于 2019/07/28 11:14:15


完全理解。确实我也经历过这段过程。其实就是不可避免的。其实看你说的情况，你现在的状态挺好的。有思路，有代码，只是有些小瑕疵，这些在OA以外的电话面试中，都是有价值的。毕竟人家考察的是你分析问题和灵...

非常谢谢楼主的指教 ~~ 要是visualizer能做成tree就好了 >_< 平时看着还挺清楚的 一到recursion 冷不丁跑了一圈数据就全变了 令人一头雾水 我平时也会自己画的 但是我画的更加乱 哈哈哈 😂 而且楼主说的先想想题目问什么 再想什么知识能用上真的非常重要 我最近在想 可能我就是先没那个知识 后面才出一堆问题 我以前是没学过数据结构的 今年要入学读DS 然后常来地里竟然就萌生了转码的心 但是我感觉时间不够能念完数据结构+算法并能在开学前刷个上百题啊 而且看到地里有人硬刷题来学习数据结构的 所以我就开始刷了 现在也200多题了 但是回想一下 一开始不会的东西 到了以后即使能做题也是没深刻理解这个算法或者模式的理念 或者一开始它是被发明出来解决什么问题的 比如dfs我的心得就是一个grid里面找一个位置然后检查上下左右 除此之外就不知道了 所以我现在也不怎么刷题了 默默回去学算法 只有把根源弄清楚 后面才知道遇到什么问题用什么工具 …

Tree -> DAG的优化问题

mchen117 发表于 2019-7-28 05:05
谢谢楼主的讲解 ~~ 楼主能不能分享一下从开始刷题 复习算法到现在取得比较大的进步中间花了多长时间呀？

...

你好！问下这个visualizer是一款工具么？名字就叫这个么？也需要这样的工具来理解一个动态算法过程，谢谢！

luckybird2015 发表于 2019/07/29 05:42:47


你好！问下这个visualizer是一款工具么？名字就叫这个么？也需要这样的工具来理解一个动态算法过程，谢谢！

是一个网站自己做的 只支持Python和Java 你可以搜索下python visualizer 首页会给出这个网站的链接 还有IntelliJ这个IDE里面有自带的visualizer

你也太牛逼了吧

感谢分享感谢分享