凡尔赛

leetcode国区开通了题解和评论，移动端更是有个讨论的入口。这个讨论跟国际版的discuss完全不同，招聘、炫耀、揭短、挂人，一应俱全，符合国内社交软件一贯的pvp特色。短时间大量刷leetcode的人大概可以分为两类，第一种是备考计算机专业（如计算机科学与技术、软件工程）的考研大军，我们能够容忍这种人，并且会喜欢、鼓励甚至保护他们；我们可以向他们传授刷题经验，指点一些数据结构方面的优化，体会倚老卖老的痛快感。还有一种是准备春招的行将毕业的应届生，这种人只会惹我们厌恶甚至嫉妒，他们即将进入职场，甚至已经在一些头部大厂实习过，早已失去尊敬打工人的基本道德，而我们的技术水平又不足以引起他们的围观和仰视；甚至于他们可能读书期间就已经拿过acm的奖牌，乃至于在b站上传过视频心得。这会儿咋咋乎乎的进入leetcode，无非是练手和熟悉企业题库；对于他们，我们非但不能倚老卖老，还要赶着他们装年轻，我们的工作履历反而使得自己吃亏，毕竟现在互联网工资倒挂，大厂也更喜欢年轻后生。这群小鲜肉写个题解还要晒晒收割的offer(s)，甚至在评论区质问你：你个老油条，工资多少？ 这两种态度使得我们特别爱劝学，恨不能让所有年轻人都读研读博最后再留校做博后，用北京人的话说，就是：在里面呆着吧你内 。
互联网的内卷是没个尽头的，而互联网领域的刷题内卷，往往是一种讽刺：吃计算机这碗饭的应该讲究实用，而内卷刷题却走着孔乙己的路数：你知道二叉树有几种遍历方式吗？除了先序中序后序外，还有一种是层次遍历哟 。

背包问题泛谈

以上的感想，有戏谑的成分。实际上刷题还是有意思的，至少能让你重温“一杯茶一包烟一道积分算一天”的酸爽。举凡刷题，离不开动态规划，而medium和easy难度的dp问题，至少60%都可以转化为背包问题。
背包问题的教程和解说在互联网泛滥，往往有互相抄袭的嫌疑。中文互联网的最早出处应该是大神崔添翼的 背包九讲 。<背包九讲>几乎考虑了资源分配类型应用题的所有情况，其中能转化为常规dp解题思路的有01背包/完全背包/多重背包/分组背包。必须装满背包的情况又涵盖在这几种背包情况之内，暂且称作为充分背包（如01充分背包、完全充分背包）。多重背包又可以借助二进制位运算进行压缩，是为状态压缩dp的滥觞。
322. 零钱兑换 是典型的充分完全背包应用题。硬币 coins 有几种面值，即相当于多种资源，总金额 amount 相当于背包容量，题目要求凑够总金额，就是填满背包。在背包填充过程中不停的保存抵达每个金额的需要的最小金币数字，一直到填充满总金额。
983. 最低票价 算是322题的升级版，由于包含天数为1的通行证，所以无论如何都可以填满背包，故可以看作完全背包。这个题目的难点是如何确定背包容量(即从旅游日子里最小的天到最大的天)，以及间隔的日子如何处理(顺延间隔前的最小费用)。核心代码如下:·

       int c1=0,c7=0,c30=0;
        for (int i = days[0]-1; i < n; i++) {//从第1个有效天开始
            if(dp[i+1]==0){//不是假期，费用延续前一天
                dp[i+1] = dp[i];
            }else {
                c1=dp[i] +costs[0];
                c7 = (i-6>=0?dp[i-6]:dp[0] )+costs[1];
                c30 = (i-30>=0?dp[i-29]:dp[0]) +costs[2];
                dp[i+1] = Math.min(c1,Math.min(c7,c30));
            }
        }

377. 组合总和 Ⅳ , 279. 完全平方数 , 139. 单词拆分 ,也是同类的题目。
其他如 718. 最长重复子数组 , 416. 分割等和子集 , 1049. 最后一块石头的重量II ,则是01背包的变型，只要能分辨出什么是资源，什么是背包就可以快速解决。
1155. 掷骰子的N种方法 则是分组背包的变型。这个题目几乎达到了背包类型题目的天花板。核心代码如下:

        for (int i = 1; i < d; i++) {//从第一个骰子依次累加
            dp_current =new int[target+1];//每一轮重置

            for (int j = 0; j <= target; j++) {//当目标是0\1\2\3-target等情况下最大值
                for (int k = 1; k <= f; k++) {//多种数字轮流测试
                    if(j-k>=0){
                        dp_current[j]  += dp_previous[j-k];//会有多种情况满足反复累加，比如4；有1+3；2+2；3+1；相当于previous[3]+previous[2]+previous[1]累加
                        if(dp_current[j]>mod)dp_current[j]%=mod;//相加就可能过大，所以在此取余
                    }
                }

            }

            dp_previous = dp_current;

        }

背包问题本身虽然简单，但是却透露着数学思维：用看似愚笨的遍历方法将指数级复杂度的难题降低到多项式复杂度。这有点像魔方，如果让计算机来模拟还原魔方，需要计算43,252,003,274,489,856,000的次数才能遍历出所有的组合情况，如果让人类去转的话，就算按照魔方高手每秒10步的手速，平均也需要1370亿年，最强大的计算机也要花费非常多的时间才能运算完成；而现实中,熟练的(三阶)魔方职业竞速选手，往往可以达到sub10(10秒以下)。职业选手当然是通过背公式(还原步数可以降低到几十步)和反复练习来提高，而如果让计算机掌握这些公式，则可以在纳秒间还原魔方。退而来说，即使不掌握公式，仅仅了解了魔方的结构（中心块、菱块、角块）和6轴颜色的分布，计算机也可以仅仅需要几万次的尝试，就可以遍历完所有的组合，花费时间也在微秒级别。魔方的例子完美的展示了在了解数据本身结构后，即使利用最笨的穷举遍历，也可以很高效地解决问题。

最长系列

leetcode收纳了几乎所有的最长系列经典题目，如最长公共子序列、最长前缀和、最长回文子串、最长回文子序列、最长上升子序列。这些题目又可以细分为两块：子序列和子串。子串要求连续，有时通过双指针或者中心发散就可以解决，子序列则必须采用dp或者必须部分借助dp思想才能解决。
5. 最长回文子串 算是这个系列最简单的题目，利用中心发散，考虑下奇偶性即可解决，虽然挂着dp的标签，其实跟dp关系不大。

Is this article useful to you? How about buy me a coffee ☕ ?