动态规划之子序列问题解题模板读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：
LeetCode
力扣
难度
1312. Minimum Insertion Steps to Make a String Palindromeopen in new window
1312. 让字符串成为回文串的最少插入次数open in new window
🔴
516. Longest Palindromic Subsequenceopen in new window
516. 最长回文子序列open in new window
🟠
子序列问题是常见的算法问题，而且并不好解决。
首先，子序列问题本身就相对子串、子数组更困难一些，因为前者是不连续的序列，而后两者是连续的，就算穷举你都不一定会，更别说求解相关的算法问题了。
而且，子序列问题很可能涉及到两个字符串，比如前文 最长公共子序列，如果没有一定的处理经验，真的不容易想出来。所以本文就来扒一扒子序列问题的套路，其实就有两种模板，相关问题只要往这两种思路上想，十拿九稳。
一般来说，这类问题都是让你求一个最长子序列，因为最短 ...
带权重的随机选择算法读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：
LeetCode
力扣
难度
528. Random Pick with Weightopen in new window
528. 按权重随机选择open in new window
🟠
-
剑指 Offer II 071. 按权重生成随机数open in new window
🟠
写这篇的文章的原因是玩 LOL 手游。
我有个朋友抱怨说打排位匹配的队友太菜了，我就说我打排位觉得队友都挺行的啊，好像不怎么坑？
朋友意味深长地说了句：一般隐藏分比较高的玩家，排位如果排不到实力相当的队友，就会排到一些菜狗。
嗯？我想了几秒钟感觉这小伙子不对劲，他意思是说我隐藏分低，还是说我就是那条菜狗？
我立马要求和他开黑打一把，证明我不是菜狗，他才是菜狗。开黑结果这里不便透露，大家猜猜吧。
打完之后我就来发文了，因为我对游戏的匹配机制有了一点思考。
所谓「隐藏分」我不知道是不是真的，毕竟匹配机制是所有竞技类游戏的核心环节，想必非常复杂，不是简单几个指标就能搞定的。
但是如果把这个「隐藏分」机制简化， ...
经典动态规划：最长公共子序列读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：
LeetCode
力扣
难度
1143. Longest Common Subsequenceopen in new window
1143. 最长公共子序列open in new window
🟠
583. Delete Operation for Two Stringsopen in new window
583. 两个字符串的删除操作open in new window
🟠
712. Minimum ASCII Delete Sum for Two Stringsopen in new window
712. 两个字符串的最小ASCII删除和open in new window
🟠
-
剑指 Offer II 095. 最长公共子序列open in new window
🟠
不知道大家做算法题有什么感觉，我总结出来做算法题的技巧就是，把大的问题细化到一个点，先研究在这个小的点上如何解决问题，然后再通过递归/迭代的方式扩展到整个问题。
比如说我们前文 ...
滑动窗口算法延伸：Rabin Karp 字符匹配算法读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：
LeetCode
力扣
难度
187. Repeated DNA Sequencesopen in new window
187. 重复的DNA序列open in new window
🟠
28. Find the Index of the First Occurrence in a Stringopen in new window
28. 找出字符串中第一个匹配项的下标open in new window
🟠
经常有读者留言，请我讲讲那些比较经典的算法，我觉得有这个必要，主要有以下原因：
1、经典算法之所以经典，一定是因为有独特新颖的设计思想，那当然要带大家学习一波。
2、我会尽量从最简单、最基本的算法切入，带你亲手推导出来这些经典算法的设计思想，自然流畅地写出最终解法。一方面消除大多数人对算法的恐惧，另一方面可以避免很多人对算法死记硬背的错误习惯。
我之前用状态机的思路讲解了 KMP 算法open in new window，说实话 KMP 算法确实 ...
一个方法团灭 LeetCode 打家劫舍问题读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：
LeetCode
力扣
难度
198. House Robberopen in new window
198. 打家劫舍open in new window
🟠
213. House Robber IIopen in new window
213. 打家劫舍 IIopen in new window
🟠
337. House Robber IIIopen in new window
337. 打家劫舍 IIIopen in new window
🟠
-
剑指 Offer II 089. 房屋偷盗open in new window
🟠
-
剑指 Offer II 090. 环形房屋偷盗open in new window
🟠
有读者私下问我 LeetCode 「打家劫舍」系列问题（英文版叫 House Robber）怎么做，我发现这一系列题目的点赞非常之高，是比较有代表性和技巧性的动态规划题目，今天就来聊聊这道题目。
打家劫舍系列总共有三道，难 ...
经典动态规划：戳气球读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：
LeetCode
力扣
难度
312. Burst Balloonsopen in new window
312. 戳气球open in new window
🔴
今天我们要聊的这道题「Burst Balloon」和之前我们写过的那篇 经典动态规划：高楼扔鸡蛋问题 分析过的高楼扔鸡蛋问题类似，知名度很高，但难度确实也很大。因此我的公众号就给这道题赐个座，来看一看这道题目到底有多难。
它是力扣第 312 题「戳气球open in new window」，题目如下：
312. 戳气球 | 力扣 open in new window | LeetCode open in new window |有 n 个气球，编号为0 到 n - 1，每个气球上都标有一个数字，这些数字存在数组 nums 中。现在要求你戳破所有的气球。戳破第 i 个气球，你可以获得& ...
经典动态规划：正则表达式读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：
LeetCode
力扣
难度
10. Regular Expression Matchingopen in new window
10. 正则表达式匹配open in new window
🔴
-
剑指 Offer 19. 正则表达式匹配open in new window
🔴
正则表达式是一个非常强力的工具，本文就来具体看一看正则表达式的底层原理是什么。力扣第 10 题「正则表达式匹配open in new window」就要求我们实现一个简单的正则匹配算法，包括「.」通配符和「*」通配符。
这两个通配符是最常用的，其中点号「.」可以匹配任意一个字符，星号「*」可以让之前的那个字符重复任意次数（包括 0 次）。
比如说模式串 ".a*b" 就可以匹配文本 "zaaab"，也可以匹配 "cb"；模式串 "a..b" 可以匹配文本 "amnb"；而模式串 ".*" ...
经典动态规划：高楼扔鸡蛋读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：
LeetCode
力扣
难度
887. Super Egg Dropopen in new window
887. 鸡蛋掉落open in new window
🔴
本文要聊一个很经典的算法问题，若干层楼，若干个鸡蛋，让你算出最少的尝试次数，找到鸡蛋恰好摔不碎的那层楼。国内大厂以及谷歌脸书面试都经常考察这道题，只不过他们觉得扔鸡蛋太浪费，改成扔杯子，扔破碗什么的。
具体的问题等会再说，但是这道题的解法技巧很多，光动态规划就好几种效率不同的思路，最后还有一种极其高效数学解法。秉承本书一贯的作风，拒绝过于诡异的技巧，因为这些技巧无法举一反三，学了也不划算。
下面就来用我们一直强调的动态规划通用思路来研究一下这道题。
#一、解析题目这是力扣第 887 题「鸡蛋掉落open in new window」，我描述一下题目：
你面前有一栋从 1 到 N 共 N 层的楼，然后给你 K 个鸡蛋（K 至少为 1）。现在确定这栋楼存在楼层 0 <= F <= N，在这层楼将鸡蛋扔下去，鸡蛋恰好没 ...
目标和：背包问题的变体读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：
LeetCode
力扣
难度
494. Target Sumopen in new window
494. 目标和open in new window
🟠
-
剑指 Offer II 102. 加减的目标值open in new window
🟠
我们前文经常说回溯算法和递归算法有点类似，有的问题如果实在想不出状态转移方程，尝试用回溯算法暴力解决也是一个聪明的策略，总比写不出来解法强。
那么，回溯算法和动态规划到底是啥关系？它俩都涉及递归，算法模板看起来还挺像的，都涉及做「选择」，真的酷似父与子。
那么，它俩具体有啥区别呢？回溯算法和动态规划之间，是否可能互相转化呢？
今天就用力扣第 494 题「目标和open in new window」来详细对比一下回溯算法和动态规划，题目如下：
给你输入一个非负整数数组 nums 和一个目标值 target，现在你可以给每一个元素 nums[i] 添加正号 + 或负号 -，请你计算有几种符号的组合能够使得 nums 中元素的和为 target ...
剪视频剪出一个贪心算法读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：
LeetCode
力扣
难度
1024. Video Stitchingopen in new window
1024. 视频拼接open in new window
🟠
前面发过几个视频，也算是对视频剪辑入了个门。像我这种非专业剪辑玩家，不做什么宏大特效电影镜头，只是做个视频教程，其实也没啥难度，只需要把视频剪流畅，所以用到最多的功能就是切割功能，然后删除和拼接视频片接。
没有剪过视频的读者可能不知道，在常用的剪辑软件中视频被切割成若干片段之后，每个片段都可以还原成原始视频。
就比如一个 10 秒的视频，在中间切一刀剪成两个 5 秒的视频，这两个五秒的视频各自都可以还原成 10 秒的原视频。就好像蚯蚓，把自己切成 4 段就能搓麻，把自己切成 11 段就可以凑一个足球队。
剪视频时，每个视频片段都可以抽象成了一个个区间，时间就是区间的端点，这些区间有的相交，有的不相交……
假设剪辑软件不支持将视频片段还原成原视频，那么如果给我若干视频片段，我怎么将它们还原成原视频呢？
🌟
🌟
这是 ...
