企业官网建设流程全解析

1. 动态规划入门：从最长上升子序列说起

动态规划（Dynamic Programming，简称DP）是算法设计中一种非常重要的思想，它通过将复杂问题分解为更小的子问题来解决。我第一次接触动态规划时，被它的精妙所震撼，但同时也被它的抽象性所困扰。今天，我们就以最长上升子序列（Longest Increasing Subsequence，LIS）问题为例，来揭开动态规划的神秘面纱。

最长上升子序列问题描述很简单：给定一个无序的整数数组，找到其中最长的严格递增子序列的长度。例如，对于数组[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)。这在n=20时就已经需要处理约2000万种可能性，显然不适用于实际问题。

2.2 寻找最优子结构

动态规划的核心思想是问题具有"最优子结构"性质：一个问题的最优解包含其子问题的最优解。对于LIS问题，我们可以观察到：

1. 以nums[i]结尾的LIS长度，取决于所有j < i且nums[j] < nums[i]的情况
2. 我们需要在这些情况中选择能形成最长序列的那个

这种性质提示我们可以使用动态规划来解决这个问题。

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)。对于n=2500（如LeetCode上的约束），这个解法是完全可行的。

4. 优化解法：贪心+二分查找

4.1 直觉与思路

虽然O(n^2)的解法已经不错，但我们可以做得更好。观察到一个关键性质：在相同长度的情况下，我们希望子序列的最后一个数尽可能小，这样后面有更多机会接上更大的数。

这提示我们可以维护一个数组tails，其中tails[i]表示长度为i+1的所有上升子序列中，结尾最小的那个数字。

4.2 算法步骤

1. 初始化tails数组为空
2. 对于每个数字num：
   • 如果num大于tails的所有元素，则将其添加到tails末尾
   • 否则，用num替换tails中第一个大于等于它的元素
3. 最终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问题。给定一些信封的宽度和高度，如果一个信封的宽度和高度都比另一个大，就可以套进去。问最多能套多少层。

解法：

1. 先对宽度升序排序，宽度相同的按高度降序排序
2. 然后在高度序列上找LIS

def maxEnvelopes(envelopes): envelopes.sort(key=lambda x: (x[0], -x[1])) heights = [h for _, h in envelopes] return lengthOfLIS(heights)

5.2 其他变种

• 最长不下降子序列（允许相等）
• 带权值的LIS（求最大权值和而非最长长度）
• 需要输出具体的LIS而不仅仅是长度

6. 动态规划的思考框架

通过LIS问题，我们可以总结出解决动态规划问题的一般步骤：

1. 定义状态：明确dp数组的含义
2. 确定初始条件（base case）
3. 建立状态转移方程
4. 确定计算顺序
5. 考虑优化空间（如滚动数组）

对于LIS问题，我们经历了从暴力解法到标准DP，再到优化解法的过程。在实际编程面试中，理解并能够实现O(n log n)的解法会给你带来很大优势。

7. 常见错误与调试技巧

在实现LIS算法时，容易犯的几个错误：

1. 错误的状态定义：比如定义dp[i]为前i个元素的LIS长度，这样难以建立状态转移
2. 忽略初始条件：每个dp[i]至少为1
3. 二分查找实现错误：注意边界条件和等号处理

调试时可以：

• 打印dp数组观察变化
• 对小例子手动计算验证
• 特别注意边界情况（空数组、单元素数组、完全逆序数组等）

8. 扩展练习

为了巩固对LIS和动态规划的理解，建议尝试以下LeetCode题目：

• 300. 最长上升子序列（基础）
• 354. 俄罗斯套娃信封问题（二维）
• 673. 最长递增子序列的个数（统计数量）
• 646. 最长数对链（变种）

记住，掌握动态规划的关键在于多练习、多思考状态的定义和转移。LIS问题作为一个经典例题，理解它对于掌握动态规划至关重要。