1. 动态规划入门从最长上升子序列说起动态规划Dynamic Programming简称DP是算法设计中一种非常重要的思想它通过将复杂问题分解为更小的子问题来解决。我第一次接触动态规划时被它的精妙所震撼但同时也被它的抽象性所困扰。今天我们就以最长上升子序列Longest Increasing SubsequenceLIS问题为例来揭开动态规划的神秘面纱。最长上升子序列问题描述很简单给定一个无序的整数数组找到其中最长的严格递增子序列的长度。例如对于数组[10,9,2,5,3,7,101,18]最长的上升子序列是[2,3,7,101]长度为4。2. 暴力解法与问题分析2.1 暴力搜索的局限性最直观的解法是枚举所有可能的子序列然后检查它们是否是上升的。对于一个长度为n的数组它有2^n个子序列每个元素可以选择包含或不包含检查每个子序列是否上升需要O(n)时间因此总时间复杂度是O(n*2^n)。这在n20时就已经需要处理约2000万种可能性显然不适用于实际问题。2.2 寻找最优子结构动态规划的核心思想是问题具有最优子结构性质一个问题的最优解包含其子问题的最优解。对于LIS问题我们可以观察到以nums[i]结尾的LIS长度取决于所有j i且nums[j] nums[i]的情况我们需要在这些情况中选择能形成最长序列的那个这种性质提示我们可以使用动态规划来解决这个问题。3. 动态规划解法详解3.1 定义状态我们定义dp[i]为以第i个数字结尾的最长上升子序列的长度。注意这个定义非常关键它决定了我们如何构建状态转移方程。例如对于数组nums [10,9,2,5,3,7,101,18]dp[2] 1以2结尾的LIS就是[2]dp[3] 2以5结尾的LIS可以是[2,5]dp[4] 2以3结尾的LIS可以是[2,3]3.2 状态转移方程对于每个i我们需要检查所有j i如果nums[j] nums[i]那么nums[i]可以接在nums[j]后面形成更长的子序列我们选择能形成最长子序列的那个j因此状态转移方程为 dp[i] max(dp[j] 1) 对所有j i且nums[j] nums[i]如果不存在这样的j则dp[i] 1子序列只包含nums[i]本身3.3 基础实现def lengthOfLIS(nums): if not nums: return 0 dp [1] * len(nums) for i in range(1, len(nums)): for j in range(i): if nums[j] nums[i]: dp[i] max(dp[i], dp[j] 1) return max(dp)这个实现的时间复杂度是O(n^2)空间复杂度是O(n)。对于n2500如LeetCode上的约束这个解法是完全可行的。4. 优化解法贪心二分查找4.1 直觉与思路虽然O(n^2)的解法已经不错但我们可以做得更好。观察到一个关键性质在相同长度的情况下我们希望子序列的最后一个数尽可能小这样后面有更多机会接上更大的数。这提示我们可以维护一个数组tails其中tails[i]表示长度为i1的所有上升子序列中结尾最小的那个数字。4.2 算法步骤初始化tails数组为空对于每个数字num如果num大于tails的所有元素则将其添加到tails末尾否则用num替换tails中第一个大于等于它的元素最终tails的长度就是LIS的长度这个替换操作可以用二分查找来高效实现。4.3 优化实现def lengthOfLIS(nums): tails [] for num in nums: # 二分查找第一个大于等于num的元素 left, right 0, len(tails) while left right: mid (left right) // 2 if tails[mid] num: left mid 1 else: right mid if left len(tails): tails.append(num) else: tails[left] num return len(tails)这个算法的时间复杂度是O(n log n)因为对于每个元素我们进行一次O(log n)的二分查找操作。5. 实际应用与变种5.1 俄罗斯套娃信封问题这是一个经典的二维LIS问题。给定一些信封的宽度和高度如果一个信封的宽度和高度都比另一个大就可以套进去。问最多能套多少层。解法先对宽度升序排序宽度相同的按高度降序排序然后在高度序列上找LISdef maxEnvelopes(envelopes): envelopes.sort(keylambda x: (x[0], -x[1])) heights [h for _, h in envelopes] return lengthOfLIS(heights)5.2 其他变种最长不下降子序列允许相等带权值的LIS求最大权值和而非最长长度需要输出具体的LIS而不仅仅是长度6. 动态规划的思考框架通过LIS问题我们可以总结出解决动态规划问题的一般步骤定义状态明确dp数组的含义确定初始条件base case建立状态转移方程确定计算顺序考虑优化空间如滚动数组对于LIS问题我们经历了从暴力解法到标准DP再到优化解法的过程。在实际编程面试中理解并能够实现O(n log n)的解法会给你带来很大优势。7. 常见错误与调试技巧在实现LIS算法时容易犯的几个错误错误的状态定义比如定义dp[i]为前i个元素的LIS长度这样难以建立状态转移忽略初始条件每个dp[i]至少为1二分查找实现错误注意边界条件和等号处理调试时可以打印dp数组观察变化对小例子手动计算验证特别注意边界情况空数组、单元素数组、完全逆序数组等8. 扩展练习为了巩固对LIS和动态规划的理解建议尝试以下LeetCode题目最长上升子序列基础俄罗斯套娃信封问题二维最长递增子序列的个数统计数量最长数对链变种记住掌握动态规划的关键在于多练习、多思考状态的定义和转移。LIS问题作为一个经典例题理解它对于掌握动态规划至关重要。
1. 动态规划入门从最长上升子序列说起动态规划Dynamic Programming简称DP是算法设计中一种非常重要的思想它通过将复杂问题分解为更小的子问题来解决。我第一次接触动态规划时被它的精妙所震撼但同时也被它的抽象性所困扰。今天我们就以最长上升子序列Longest Increasing SubsequenceLIS问题为例来揭开动态规划的神秘面纱。最长上升子序列问题描述很简单给定一个无序的整数数组找到其中最长的严格递增子序列的长度。例如对于数组[10,9,2,5,3,7,101,18]最长的上升子序列是[2,3,7,101]长度为4。2. 暴力解法与问题分析2.1 暴力搜索的局限性最直观的解法是枚举所有可能的子序列然后检查它们是否是上升的。对于一个长度为n的数组它有2^n个子序列每个元素可以选择包含或不包含检查每个子序列是否上升需要O(n)时间因此总时间复杂度是O(n*2^n)。这在n20时就已经需要处理约2000万种可能性显然不适用于实际问题。2.2 寻找最优子结构动态规划的核心思想是问题具有最优子结构性质一个问题的最优解包含其子问题的最优解。对于LIS问题我们可以观察到以nums[i]结尾的LIS长度取决于所有j i且nums[j] nums[i]的情况我们需要在这些情况中选择能形成最长序列的那个这种性质提示我们可以使用动态规划来解决这个问题。3. 动态规划解法详解3.1 定义状态我们定义dp[i]为以第i个数字结尾的最长上升子序列的长度。注意这个定义非常关键它决定了我们如何构建状态转移方程。例如对于数组nums [10,9,2,5,3,7,101,18]dp[2] 1以2结尾的LIS就是[2]dp[3] 2以5结尾的LIS可以是[2,5]dp[4] 2以3结尾的LIS可以是[2,3]3.2 状态转移方程对于每个i我们需要检查所有j i如果nums[j] nums[i]那么nums[i]可以接在nums[j]后面形成更长的子序列我们选择能形成最长子序列的那个j因此状态转移方程为 dp[i] max(dp[j] 1) 对所有j i且nums[j] nums[i]如果不存在这样的j则dp[i] 1子序列只包含nums[i]本身3.3 基础实现def lengthOfLIS(nums): if not nums: return 0 dp [1] * len(nums) for i in range(1, len(nums)): for j in range(i): if nums[j] nums[i]: dp[i] max(dp[i], dp[j] 1) return max(dp)这个实现的时间复杂度是O(n^2)空间复杂度是O(n)。对于n2500如LeetCode上的约束这个解法是完全可行的。4. 优化解法贪心二分查找4.1 直觉与思路虽然O(n^2)的解法已经不错但我们可以做得更好。观察到一个关键性质在相同长度的情况下我们希望子序列的最后一个数尽可能小这样后面有更多机会接上更大的数。这提示我们可以维护一个数组tails其中tails[i]表示长度为i1的所有上升子序列中结尾最小的那个数字。4.2 算法步骤初始化tails数组为空对于每个数字num如果num大于tails的所有元素则将其添加到tails末尾否则用num替换tails中第一个大于等于它的元素最终tails的长度就是LIS的长度这个替换操作可以用二分查找来高效实现。4.3 优化实现def lengthOfLIS(nums): tails [] for num in nums: # 二分查找第一个大于等于num的元素 left, right 0, len(tails) while left right: mid (left right) // 2 if tails[mid] num: left mid 1 else: right mid if left len(tails): tails.append(num) else: tails[left] num return len(tails)这个算法的时间复杂度是O(n log n)因为对于每个元素我们进行一次O(log n)的二分查找操作。5. 实际应用与变种5.1 俄罗斯套娃信封问题这是一个经典的二维LIS问题。给定一些信封的宽度和高度如果一个信封的宽度和高度都比另一个大就可以套进去。问最多能套多少层。解法先对宽度升序排序宽度相同的按高度降序排序然后在高度序列上找LISdef maxEnvelopes(envelopes): envelopes.sort(keylambda x: (x[0], -x[1])) heights [h for _, h in envelopes] return lengthOfLIS(heights)5.2 其他变种最长不下降子序列允许相等带权值的LIS求最大权值和而非最长长度需要输出具体的LIS而不仅仅是长度6. 动态规划的思考框架通过LIS问题我们可以总结出解决动态规划问题的一般步骤定义状态明确dp数组的含义确定初始条件base case建立状态转移方程确定计算顺序考虑优化空间如滚动数组对于LIS问题我们经历了从暴力解法到标准DP再到优化解法的过程。在实际编程面试中理解并能够实现O(n log n)的解法会给你带来很大优势。7. 常见错误与调试技巧在实现LIS算法时容易犯的几个错误错误的状态定义比如定义dp[i]为前i个元素的LIS长度这样难以建立状态转移忽略初始条件每个dp[i]至少为1二分查找实现错误注意边界条件和等号处理调试时可以打印dp数组观察变化对小例子手动计算验证特别注意边界情况空数组、单元素数组、完全逆序数组等8. 扩展练习为了巩固对LIS和动态规划的理解建议尝试以下LeetCode题目最长上升子序列基础俄罗斯套娃信封问题二维最长递增子序列的个数统计数量最长数对链变种记住掌握动态规划的关键在于多练习、多思考状态的定义和转移。LIS问题作为一个经典例题理解它对于掌握动态规划至关重要。
