lucifer

我在动态规划专题反复强调了先学习递归,再学习记忆化,最后再学动态规划

其中原因已经讲得很透了,相信大家已经明白了。如果不明白,强烈建议先看看那篇文章。

尽管很多看了我文章的小伙伴知道了先去学记忆化递归,但是还是有一些粉丝问我:“记忆化递归转化为动态规划老是出错,不得要领怎么办?有没有什么要领呀?”

今天我就来回答一下粉丝的这个问题。

实际上我的动态规划那篇文章已经讲了将记忆化递归转化为动态规划的大概的思路,只是可能不是特别细,今天我们就尝试细化一波

我们仍然先以经典的爬楼梯为例,给大家讲一点基础知识。接下来,我会带大家解决一个更加复杂的题目。

​ 去年的一年时间,我在群里每天都会出题给大家做。但是就在 2020-03 开始,力扣也开展了每日一题活动。我突然觉得这个每日一题的必要性变得小了很多,并且逐渐减少了出题频率。但是我还是不愿意放弃大家一起集中进行交流学习的机会。于是我打算新开辟一个专题,这个专题一方面要和力扣官方的每日一题重合度低,另一方面要让大家有参与的热情。

于是【异议!】系列应运而生。它是个什么东西呢?我相信大家一定在平时刷算法的过程中,一定遇到过“这解法怎么想到的?”,“这解法不对吧?”的情况,并且可悲的是没有人能够回答你。来这里,「力扣加加」 来回答你。我们会对大家提出的问题进行筛选,将有意义的问题开放出来给大家讨论和学习。

本次给大家带来的/是【异议!】系列「第二弹」。

本文是我的 91 算法第一期的部分讲义内容。 91 算法第一期已经接近尾声,二期的具体时间关注我的公众号即可,一旦开放,会第一时间在公众号《力扣加加》通知大家。

动态规划可以理解为是查表的递归(记忆化)。那么什么是递归?什么是查表(记忆化)?

之前出了一篇穿上衣服我就不认识你了?来聊聊最长上升子序列,收到了大家的一致好评。今天给大家带来的依然是换皮题 - 最长公共子序列系列。

最长公共子序列是一个很经典的算法题。有的会直接让你求最长上升子序列,有的则会换个说法,但最终考察的还是最长公共子序列。那么问题来了,它穿上衣服你还看得出来是么?

如果你完全看不出来了,说明抽象思维还不到火候。经常看我的题解的同学应该会知道,我经常强调抽象思维。没有抽象思维,所有的题目对你来说都是新题。你无法将之前做题的经验迁移到这道题,那你做的题意义何在?

虽然抽象思维很难练成,但是幸好算法套路是有限的,经常考察的题型更是有限的。从这些入手,或许可以让你轻松一些。本文就从一个经典到不行的题型《最长公共子序列》,来帮你进一步理解抽象思维

注意。 本文是帮助你识别套路,从横向上理清解题的思维框架,并没有采用最优解,所有的题目给的解法可能不是最优的,但是都可以通过所有的测试用例。如果你想看最优解,可以直接去讨论区看。或者期待我的深入剖析系列

最长上升子序列是一个很经典的算法题。有的会直接让你求最长上升子序列,有的则会换个说法,但最终考察的还是最长上升子序列。那么问题来了,它穿上衣服你还看得出来是么?

如果你完全看不出来了,说明抽象思维还不到火候。经常看我的题解的同学应该会知道,我经常强调抽象思维。没有抽象思维,所有的题目对你来说都是新题。你无法将之前做题的经验迁移到这道题,那你做的题意义何在?

虽然抽象思维很难练成,但是幸好算法套路是有限的,经常考察的题型更是有限的。从这些入手,或许可以让你轻松一些。本文就从一个经典到不行的题型《最长上升子序列》,来帮你进一步理解抽象思维

注意。 本文是帮助你识别套路,从横向上理清解题的思维框架,并没有采用最优解,所有的题目给的解法都不是最优的,但是都可以通过所有的测试用例。如果你想看最优解,可以直接去讨论区看。或者期待我的深入剖析系列


博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本站使用 Material X 作为主题 。
载入天数...载入时分秒...