我一直都很敬重这位大佬，这位大佬的算法水平远在我之上，我真的望尘莫及。整个过程，我也都是在讨论技术问题，但是最后从大佬那里感受到了深深的鄙视，让我有点难过，爱恨交织。

并且也不要把本帖当成吃瓜贴，我保证看完此文，你会对动态规划有更深的认识。

1. 起因：扯几句动态规划

2. 事情的经过

   1. 第一个回合
   2. 第二个回合
   3. 第三个回合
   4. 第四个回合

3. 后记

起因：扯几句动态规划

不知道动态规划（简称dp）是不是其他人的噩梦，但是肯定曾经是我的噩梦。每次当我信心满满以为我掌握了动态规划时，总是被Leetcode中的下一道动态规划题狠狠打脸。

事情的起因与动态规划的定义有关。不知道大家刷题有没有这样的感觉，有时候遇到相对简单的题，自己解出来了，然后一看题解，发现总有人声称可以用动态规划来解，评论区都是惊呼大神。

这个时候你会感觉眼前一黑，惊叹"好家伙，怎么又是动态规划题👻，这不是用核武器炸鱼吃吗？节省点核武器不好吗？"。但如果你仔细看这些题解，发现本质上就是个简单的递归或迭代，只是套了一层dp的皮。

我这个人吧，又比较爱较真。根据我啃《算法导论》中动态规划章节得出的结论，我觉得一个问题适用动态规划，有两个前提：

1. 问题具有最忧的子结构。也就是若干个子问题的最优解通过某种运算，可以得出主问题的最优解。
2. 需要求解重叠的子问题。也就是多个规模更大的问题，都依赖相同规模更小的子问题。

所以对于只依赖一个子问题的情形，我觉得不属于动态规划的范畴。比如求解等比数列的第n个值，有递推公式$a_n=2a_{n-1}$，规模为n的问题，只依赖规模为n-1的一个子问题，这个时候如果有人生成需要用dp来解(见下面代码中的method1)，我想你很难不眼前一黑：

/**
求等比数列的第n个数，要求不用数学上的通项公式。
 */
class Solution {
    /** 
    强行动态规划，让人眼前一黑的操作
    空间复杂度O(n)
    */
    public int method1(int n, int a1, int q) {
        int dp[] = new int[n + 1];
        dp[1] = a1;
        for(int i = 1; i <= n; i++){
            dp[i] = q * dp[i - 1];
        }
        return dp[n];
    }

    /**
     正常解法，空间复杂度O(1)
     */
    public int method2(int n, int a1, int q) {
        int ret = a1;
        for(int i = 1; i <= n; i++){
            ret *= q;
        }
        return ret;
    }
}

我觉得大部分人应该都会用上面的method2吧，这样不但更容易想到，而且空间复杂度也需要O(1)即可。

这种强行动态规划的做法，有人给他起了个名字叫：线性动态规划、线性dp。

我搜遍了互联网，也没找到这种叫法的权威来源。中文互联网上，确实有很多博客里这么叫，但都是抄来抄去，找不到原始出处。我用英文搜索Linear Dynamic Programming，也搜不到对应的结果。我猜测这个概念是某些培训机构发明的，传来传去，以讹传讹，就变成这样了。

事情的经过

第一个回合

2022年11月20日，我做完了当天的每日一题「799. 香槟塔」，习惯性的看了官解，并瞄了一眼大家的题解。

好死不死，有一位大佬的帖子 《简单线性 DP 运用题》 赫然映入了我的眼帘。大佬的解法是这样的：

我这个人吧，学习的时候是真的比较爱较真，当时自然又是眼前一黑。如果用简单的迭代或递归，这道题只需要$O(n)$的空间，而大佬的写法，需要$O(n^2)$。

但不同于以往，这次我鬼使神差的实在没憋住，因为这是我经常关注的一位大佬，我忍不住就留言了：

我觉得的这不叫dp。或者说，楼主大佬说的线性dp就是普通的递归或迭代。

dp用来解决具有最优子结构的问题，且一个问题需要依赖规模更小的多个子问题，这些子问题的规模不确定。

当然，这只是个概念定义的问题，我是按照《算法导论》中的介绍来理解的。我看到还有人说dp分为一元dp、二元dp、三元dp……，让我感到很头秃

我记得上一次，我给这位大佬留言，他还给我点了个赞，我别提多开心了🤣。这一次，内心还有点小期待呢。

我的留言里列出了我眼中动态规划的适用场景。我向来害怕撕x吵架，所以我还特地强调了这只是个概念定义的问题，只是我的个人观点，避免让我尊重的大佬不悦。一些通用的技术概念，其内涵本来就是在历史上慢慢固定的，不同文献可能有不同的叫法。又好比山东人叫土豆是"地蛋"，我们山西人叫"山药"，植物学家叫"马铃薯"🐶🐶，普通话里”山药“是另一种和马铃薯没关系蔬菜。

而且我真的不是无理取闹，我这条留言有五个人点赞，被Leetcode精选了。可见，确实有很多人，和我一样，对用dp解这道题是困惑的。

如果大佬没理我，那也不会有后来眼前更黑的事情了。可是，大佬回复我了：

这是 bfs 求拓扑序的过程 当然是 dp

第二个回合

大佬的这条回复，简洁，明快，标点符号都省了，可见当时很忙。

但大佬的回复，这次没让我开心。我的眼前陷入了更深的黑。(ÒωÓױ)！纳尼，bfs？拓扑排序？

我那两天，正在重新学习图论，被《算法导论》中图论那几节折磨的欲生欲死。我实在想不到这道题和广度优先搜索bfs、和拓扑排序有关系，更想不到动态规划和这两者有啥关系。

那天我还正好解了一道拓扑排序相关的困难题，心中美滋滋的。

这就是我和大佬的区别了。我也是后知后觉，动态规划和图论确实是有关系的。当然这是后话了，在当时那个时间节点，我真的是心中一万张黑人问号.jpg。

而且，我的留言中明确提到了适用动态规划的两个条件：最优子结构和重叠子问题，算是有理有据，可大佬直接无视我的论据，甩了两个八竿子打不着的概念，还用了语气助词"当然是"，给我一种很坚定的、不容置疑、有点小霸道小不屑的感觉🤣。

我这个人吧，还是有点傲气（傻气）在身上的，一下子想起了b站那个梗：我刚练的擒拿术，哦不，我刚练的拓补排序，我能认输吗？

既然大佬无视了我的论据，我就再强调一次，还引用了维基百科的一段，话证明我不是瞎编的：

虽然楼主是大佬，但是我不同意。🐶🐶🐶🐶🐶。这两天正好在学习拓扑排序，不管使用bfs还是dfs，我都不觉得拓扑排序和动态规划有啥关系。楼主说的可能是图论中的全局最短路径问题，这确实是用动态规划求解的。

这是来自维基百科的定义，和《算法导论》中的定义是一致的：

动态规划（英语：Dynamic programming，简称DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

动态规划常常适用于有重叠子问题[1]和最优子结构（英语：Optimal substructure）性质的问题，动态规划方法所耗时间往往远少于朴素解法。

动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。

通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。

动态规划在查找有很多重叠子问题的情况的最优解时有效。它将问题重新组合成子问题。为了避免多次解决这些子问题，它们的结果都逐渐被计算并被保存，从简单的问题直到整个问题都被解决。因此，动态规划保存递归时的结果，因而不会在解决同样的问题时花费时间。

动态规划只能应用于有最优子结构的问题。最优子结构的意思是局部最优解能决定全局最优解（对有些问题这个要求并不能完全满足，故有时需要引入一定的近似）。简单地说，问题能够分解成子问题来解决。

具体到这个问题，流经第n+1行中每个杯子的流量的列表，只依赖于流经第n行的，不会依赖第于更靠前的行。所以这就是个普通的迭代或递归。此外，我也实在刻画不出这道题的其最优子结构性质。

为了证明我不是杠精，我回复大佬时，还加了一串可爱的狗头。我本来是加了一串可爱的笑脸的，但是又害怕大佬认为我是在嘲笑他，所以换成了狗头。我太难了。

我以为大佬一定会默默表扬我的认真，根本没期待大佬会再次回复我。我也没有想到，接下来直接翻车了。

第三个回合

这是一位很有个性的大佬。这次大佬的回复很长，不过依然没有标点符号：

拓扑图的特点之一在于无环 与 DP 前提之一「无后效性」相对应

从起始状态逐步转移到目标状态 本质就是在求拓扑序

更具体的 任何与最值相关的 DP 问题 本质都对应求拓扑图的最短路和最长路

而求拓扑序的两大形式 BFS 和 DFS 其实就是对应了普通递推的 DP 和基于递归的记忆化搜索

至于你的观点/原话「具体到这个问题，流经第n+1行中每个杯子的流量的列表，只依赖于流经第n行的，不会依赖第于更靠前的行。所以这就是个普通的迭代或递归」是错误的 如果根据「某个状态所依赖哪些前驱」来判断是否为属于 dp 范畴 可以说风牛马不相及

实际上绝大数的线性 DP 都有这样的特点（f[i] 仅依赖于 f[i - 1] 或 f[i + 1]） 因此都能使用「滚动数组」或「有限变量」的方式进行空间优化

这是由将状态视为点 状态之间的可转移视为边 形成的拓扑图的形状所决定的性质

至于最优子问题 其实就是状态转移方程 状态转移方程就是最优子问题的最好体现

大佬的回复，一开始让我有点烦躁。因为直觉告诉我，大佬再次完全忽略了我的论据：适用动态规划的两个前提，是最优子结构和重叠子问题，而且除了图论，大佬还甩出了更多的概念："无后效应"、"滚动数组"、"有限变量"。

并且大佬篡改了我的意思，说我"根据「某个状态所依赖哪些前驱」来判断是否为属于dp范畴，可以说风牛马不相及"。我的本意明明是：流经第n+1行的杯子的流量的列表，只依赖流经第n行的，所以根本没有任何重叠的子问题需要求解。重叠的子问题才是dp的前提啊，我的表达真的有问题吗？忧伤。很忧伤。我刚练的擒拿术，哦不，我刚练的拓扑排序，我能认输吗？

但是我这个人吧，还是比较谦虚的。大佬通篇新概念，我先搞清楚她说了个啥意思再说，说不定讲算法的书有不同的流派也未可知。我本科是学心理学的，心理学就有不同的流派。我先搞清大佬属于哪个流派。

这样想着，我猛然就记起，动态规划和图论，貌似确实是有关系的。记得很多年前，我刚啃《算法导论》中的动态规划那一章时，里面有一页好像提到了子问题图这么个东东；但我当时对图论一知半解，决定先跳过那一页，这一跳，好多年就过去了。

我意识到，我可能翻车了，好丢人哈哈哈。我颤抖着翻开了算法导论那一页，果不其然：

我瞬间感觉升华了，我对动态规划的理解更上一层楼了。子问题图的顶点，对应着动态规划中不同规模的子问题，子问题图的边，对应着大问题对小问题的倚赖，一个大问题可以倚赖多个小问题，不同的大子问题可以倚赖同一个小子问题。

采用递归进行自上而下的、带缓存的动态规划，相当于对子问题图进行深度优先遍历dfs，而自下而上不需要递归的动态规划，相当于对子问题图进行广度优先遍历dfs。

而那种让我眼前一黑的所谓线性dp，其实就是子问题图退化成了个单链表。出列链表可比处理图简单多了，简单的递归或者迭代即可。

好棒的感觉，太棒了，大佬就是大佬，果然比我高好几个level👍👍👍。

大佬讲的好多概念，我都没在《算法导论》里见到，所以好奇心发作了，更好奇大佬是哪个流派了。比如大佬说的拓扑图这个叫法，我不知道权威出处，百度和google也没给我满意的解答。我上一次接触拓扑图的概念，还是刚毕业时，公司要用d3.js渲染一些网状的动画。我只能在搜索引擎里找到一些拓扑学、拓扑结构图、网络拓扑、网络拓扑图之类的东西。

我这个人吧，有点掉书袋，强迫症法做起来我自己都控制不了，特别想搞清楚权威来源，自己也去系统地学习一下这个流派🤣。

而且我这个人吧，是真的真的有些较真在身上的。转念一想，大佬借助图论理解动态规划，确实是很精彩。可是就算是大佬，也不能用降维打击的方式，模糊焦点啊。我纠结的是："所谓的线性dp"，根本就不是dp，除了听起来逼格高点，真的是只能带来困惑，特别是给我这样的小白带来困惑。

于是，我又回复了，并且很快就自取其辱了：

首先声明一下，我不是杠精，我只是和楼主大大交流一下dp的概念。🤣

楼主对于拓扑排序和动态规划关系、dfs和自下而上的dp的关系、bfs和自上而下带记忆缓存的dp的关系的论述，我是部分同意的。动态规划可以借助『子问题图』来理解。『子问题图』是有向图，子问题的规模是图的顶点，大问题对小问题的依赖是有向边。我姑且把楼主说的『拓扑图』当成就是有向无环图，对应于我说的『子问题图』，否则又要开始一场针对『拓扑图』的无聊的”形名之辩“。

判断是否是dp，只有两个前提条件：最优子结构和重复的子问题。楼主不要篡改我的意思，我从来没有“根据「某个状态所依赖哪些前驱」来判断是否为属于 dp 范畴”。

『线性dp』的叫法，在中文互联网上很流行，但是我没找到文献出处。我能找到的可能的原始出处，是leetcode讲线性规划的那本leetbook，可能是这本leetbook原创后，被中文技术博主们来回抄袭，人云亦云。搜索Linear Dynamic Programming，找不到任何结果。如果楼主能找到原始文献，欢迎打我的脸。

抛开”名“，关注”实“，所谓的『线性dp』，其实就是『子问题图』退化成了单向链表。链表、树、森林，当然都是图，没毛病，但是在动态规划的语境下，这样有何意义呢？单链表本身就已经做好拓扑排序了。

我反对万题皆dp。我反对篡改概念的内涵和外延。否则最后只能变成自说自话、东拉西扯 、顾左右而言他，无论用自然语言交流，还是做学术研究，都是这样。

第四个回合

我一直想把焦点聚集在dp的概念上。我不觉得的所谓线性dp是dp，我很想搞清这种叫法的权威来源。大佬一直在忽略我的论据，篡改我的意思，模糊我的焦点。

我承认，我在回复的时候稍微有点情绪了，特别是最后那句"我反对万题皆dp。我反对篡改概念的内涵和外延。否则最后只能变成自说自话、东拉西扯 、顾左右而言他，无论用自然语言交流，还是做学术研究，都是这样"。

但是我觉得，我还是努力把留言控制在技术讨论的范围里。我的本意，也绝对不是做一只杠精。我只是比较执著，喜欢打破砂锅问到底。

然后我就迎来了大佬的"王之蔑视"，他回复我：

拓扑图就是指有向无环图，不用「姑且当做」，看来你的拓扑图的基本了解不到位

1. 没有篡改，「具体到这个问题，流经第n+1行中每个杯子的流量的列表，只依赖于流经第n行的，不会依赖第于更靠前的行。所以这就是个普通的迭代或递归」是你的原话，任谁看都是「都是一个“因为 - 所以”的表述」
2. 线性dp 的最早源于 lyd 的蓝书，并且作为了 0x51 章节名，你溯源居然是溯源到 LeetBook，并觉得其是最早出处？我不认为所谓写 Leetbook 的人有什么水平定义出一个广泛流传的概念（虽我也是 LB 作者
3. 区分出一个线性 DP 当然极具意义，其相比于其他 dp 来说，拓扑关系由给定数据所规定，这导致了线性 DP 的状态定义和转移都十分显然，也导致一些“非线性”的 DP 问题需要引入额外的数据结构或性质来找到某个状态所依赖的前驱，例如单调队列优化 DP、斜率优化 DP、插头 DP 等等
4. 同时「插头 DP」概念由 CDQ 所总结提出 如果按照你所说的「根据能否 search 到对应的英文含义」那估计到你这里也是一个不存在的概念
5. 我不玩文字游戏 你可以看到我的回答 都是「重解析 少名词 从不带自我感受」我建议不要说什么「有何意义」的话 只会显得无知 并且我对于你提出的这些争论毫无兴趣 你两篇回答要么是说都是名词概念的事 还混杂了个人感受 之所以回复 只是不想你说提出的概念 误导了我的读者

特此声明：本层首回复的「对于 DP 和 DAG 的简单关系」均为正确理解 并非“部分正确”

大佬显然是怒了，我从大佬的回复里，感受到了深深轻蔑和不屑，就仿佛飞鸟轻笑井蛙的眼界，又好比格陵兰鲨哂笑蜉蝣的懵懂。这位大佬是有些傲气在身上的。

大佬说了更多我听不懂的概念，而且用的都是缩写。比如lyd的蓝书、CDQ、DAG、单调队列优化DP、斜率优化DP、插头DP 。我真的彻底懵逼了。这是真·降维·核武打击。要不是我脸皮厚，我就要哭了。

我最害怕的就是看到这些缩写。不过大佬虽然不屑，但总算是给了我线索。

我本来就是抱着学习的态度来的，我承认自己的浅薄。于是我去搜索了大佬的这些概念。lyd的蓝书，原来是一本叫做《算法竞赛进阶指南》的书，豆瓣评分高达9.5，这本书里对动态规划做了更加详细的分类：

线性DP、单调队列优化DP、斜率优化DP、插头DP，都来自这本书。我终于找到了线性DP这个概念的权威来源，开心。我在豆瓣的书评厉害发现，Leetcode的另一位大佬@endlesscheng评价这本书说："我吹爆这本书，相比入门经典和挑战，这本书真正做到了详略得当，题目的深度上也更胜一筹"。

我终于知道大佬是什么流派的了，大佬是竞赛派的🤣，好厉害。而我属于只知道《算法导论》的坐井观天派的🤣。我要进化。

能怎么办呢？当然是我也立刻买了这本书😜。

至于CDQ，经过搜索，发现是一位叫做陈丹琦的中国女天才，发声明了插头dp和CDC分治，被保送清华，是斯坦福大学计算机科学博士。这是真·华人之光。

有则改之，无则加勉，无知就要多学习。我最后发自内心地感谢了大佬，并且请教了一下关于"拓扑图"的问题：

感谢大佬回复，带我进入了完全陌生的领域。确实是我孤陋寡闻了。见笑了见笑了😜😜

大佬说的lyd蓝书和CDQ，我确实不知为何物。去搜了一下，前者是一本《算法竞赛进阶指南》的书，豆瓣评分高达9.5，里面对dp做了进一步分类。我已购买本书🐶。CDQ是一位叫做陈丹琦的中国女天才，发声明了插头dp和CDC分治，被保送清华，是斯坦福大学计算机科学博士。回头我也学一下这位华人天才的发明🤣

我是一个只读过《大话数据结构》和《算法导论》，初来leetcode练级的普通程序员。其实我只是对线性dp的概念有异议，本是抱着追本溯源、融会贯通的态度来的。一开始对线性dp的叫法，觉得多此一举，但又苦于找不到原始出处，只能看到网上人云亦云的复述，感觉有点烦躁。

我从楼主大佬的回复里，感受到了深深轻蔑和不屑，就仿佛飞鸟轻笑井蛙的眼界，又好比格陵兰鲨哂笑蜉蝣的懵懂。

但是依然感谢楼主的回复，获益良多。🐶🐶。最后再厚脸皮请教一下，拓扑图这个概念，哪本权威文献里能找到，我去学习一下。

后记

我膜拜权威，但是我从不迷信权威。我勤学不倦，别人对我的评价，从来都是有则改之，无则加勉。

大佬说没篡改我的愿意，那就没篡改吧，虽然我觉得是真的是篡改了，那确实是一个「因为……所以句式」，但是「因为」的前提，是基于"重叠的子问题"这个动态规划的适用条件，我不觉得的我说错了。人类只能用文字交流，我也很绝望，什么时候能心电感应就好了。

大佬建议我"不要说什么「有何意义」的话 只会显得无知"，我承认我是初学算法，比较无知，但是我无知，并不是因为我追问"线性dp"的来源和意义而无知。一个广为流传的概念，如果不正本清源，那才可怕，我不觉得这样是无意义的。评论区有那么多人，因为这个线性dp的叫法而懵逼，就能说明问题。

大佬说最后那句"我对于你提出的这些争论毫无兴趣 你两篇回答要么是说都是名词概念的事 还混杂了个人感受 之所以回复 只是不想你说提出的概念 误导了我的读者"，是真的让我很难过。他的不屑之意跃然纸上，担心我会误导了他的读者，但是我也是他的读者啊。这句话真的一万点暴击，有一种我被抛弃了、我很想黑化的感觉。

大佬最后没再回复我关于"拓扑图"的新问题，看来我需要自己查资料了。如果有知道的朋友，可以告诉我一下。

但是我真的很感激他，他让我知道了动态规划和图论的关系、让我知道了《算法竞赛进阶指南》这本书、让我知道了陈丹琦的故事。

感恩，真的感恩。

最后，这位大佬不是他，而是她。@AC_OIer。

今天，她发帖说要离开leetcode了，我看了以后还是很难过的。我曾经读过她的另一篇帖子《随手一写又没什么逻辑的碎碎念，就当留个纪念儿吧》，从中可以看到这是一位很认真、很能坚持的大佬。她的贴子中说：

其实中途（包括最近）也想过不更了，尤其是遭遇一些恶意拉踩、私信发脏话、在其他题解评论区被内涵或者发现平台对内容认可标准与自身冲突的时刻，感觉最强烈的时候，是真的会说出一天都不想写了，结果到最后可能又被几位小伙伴的劝导和大家的热情中盖过去。

希望她不要认定，我是她讨厌的这些人中的一员。也希望，她能经常回Leetcode看看。我爱leetcode，这是我见过的最喜欢的社区。

我也会继续努力，让自己从小白变成大佬。