企业官网建设流程全解析

1. LeetCode Hot 100 动态规划专题解析

动态规划（Dynamic Programming）是算法面试中的高频考点，也是LeetCode Hot 100中的重点题型。这个专题将深入剖析动态规划的核心解题思路，通过典型例题帮助掌握这一重要算法范式。

动态规划本质上是一种"空间换时间"的优化技术，通过将问题分解为相互重叠的子问题，并存储子问题的解来避免重复计算。在LeetCode Hot 100中，动态规划问题占比约15-20%，是必须掌握的算法类型。

2. 动态规划解题框架

2.1 动态规划三要素

任何动态规划问题都包含三个核心要素：

1. 最优子结构：问题的最优解包含子问题的最优解
2. 重叠子问题：递归求解时会重复计算相同的子问题
3. 状态转移方程：定义如何从一个状态推导出下一个状态

2.2 解题四步法

解决动态规划问题的标准流程：

1. 定义dp数组的含义
2. 确定初始条件(base case)
3. 推导状态转移方程
4. 确定遍历顺序和边界条件

以经典的爬楼梯问题(LeetCode 70)为例：

• dp[i]表示爬到第i阶楼梯的方法数
• 初始条件：dp[0]=1, dp[1]=1
• 状态转移：dp[i] = dp[i-1] + dp[i-2]
• 遍历顺序：从i=2开始正向遍历

3. 典型问题分类解析

3.1 单序列问题

这类问题的输入通常是一个数组或字符串，需要在单维度上进行状态转移。

例题：最长递增子序列(LeetCode 300)

def lengthOfLIS(nums): dp = [1] * len(nums) for i in range(1, len(nums)): for j in range(i): if nums[i] > nums[j]: dp[i] = max(dp[i], dp[j]+1) return max(dp)

关键点：

• dp[i]表示以nums[i]结尾的最长递增子序列长度
• 双重循环比较所有前面的元素
• 时间复杂度O(n²)，可用二分查找优化到O(nlogn)

3.2 双序列问题

涉及两个输入序列的对比或匹配，如字符串编辑距离、最长公共子序列等。

例题：编辑距离(LeetCode 72)

def minDistance(word1, word2): m, n = len(word1), len(word2) dp = [[0]*(n+1) for _ in range(m+1)] for i in range(m+1): dp[i][0] = i for j in range(n+1): dp[0][j] = j for i in range(1, m+1): for j in range(1, n+1): if word1[i-1] == word2[j-1]: dp[i][j] = dp[i-1][j-1] else: dp[i][j] = 1 + min( dp[i-1][j], # 删除 dp[i][j-1], # 插入 dp[i-1][j-1] # 替换 ) return dp[m][n]

关键点：

• dp[i][j]表示word1前i个字符转换为word2前j个字符的最小操作数
• 初始化第一行和第一列表示空字符串的转换代价
• 状态转移考虑三种操作的最小代价

3.3 背包问题

经典的背包问题及其变种，包括0-1背包、完全背包、多重背包等。

例题：分割等和子集(LeetCode 416)

def canPartition(nums): total = sum(nums) if total % 2 != 0: return False target = total // 2 dp = [False] * (target + 1) dp[0] = True for num in nums: for i in range(target, num-1, -1): dp[i] = dp[i] or dp[i - num] return dp[target]

关键点：

• 转化为0-1背包问题，背包容量为sum/2
• dp[i]表示能否凑出和为i的子集
• 内层循环需要倒序，避免重复计算

3.4 状态机问题

这类问题中状态转移较为复杂，可能需要定义多个状态或状态转移图。

例题：买卖股票的最佳时机(LeetCode 121-123系列)

# 买卖股票的最佳时机III(LeetCode 123) def maxProfit(prices): buy1 = buy2 = float('-inf') sell1 = sell2 = 0 for price in prices: buy1 = max(buy1, -price) sell1 = max(sell1, buy1 + price) buy2 = max(buy2, sell1 - price) sell2 = max(sell2, buy2 + price) return sell2

关键点：

• 维护四个状态变量表示第一次买入/卖出和第二次买入/卖出的最大利润
• 状态转移方程需要考虑前一个状态的影响
• 空间复杂度优化到O(1)

4. 动态规划优化技巧

4.1 空间复杂度优化

许多动态规划问题可以将二维dp数组优化为一维，甚至用几个变量表示。

示例：斐波那契数列

def fib(n): if n < 2: return n a, b = 0, 1 for _ in range(2, n+1): a, b = b, a + b return b

4.2 记忆化搜索

自顶向下的递归解法配合缓存，有时比自底向上的迭代更直观。

示例：不同路径II(LeetCode 63)

def uniquePathsWithObstacles(grid): m, n = len(grid), len(grid[0]) memo = {} def dfs(i, j): if (i,j) in memo: return memo[(i,j)] if i >= m or j >= n or grid[i][j] == 1: return 0 if i == m-1 and j == n-1: return 1 memo[(i,j)] = dfs(i+1, j) + dfs(i, j+1) return memo[(i,j)] return dfs(0, 0)

4.3 状态压缩

对于状态数量有限的问题，可以用位运算等技巧压缩状态表示。

示例：旅行商问题(TSP)

def tsp(graph): n = len(graph) VISITED_ALL = (1 << n) - 1 dp = [[float('inf')] * n for _ in range(1<<n)] for i in range(n): dp[1<<i][i] = 0 for mask in range(1<<n): for last in range(n): if not (mask & (1<<last)): continue for curr in range(n): if mask & (1<<curr): continue new_mask = mask | (1<<curr) dp[new_mask][curr] = min( dp[new_mask][curr], dp[mask][last] + graph[last][curr] ) return min(dp[VISITED_ALL][i] + graph[i][0] for i in range(n))

5. 高频动态规划问题清单

5.1 基础必刷题

• 70. 爬楼梯
• 198. 打家劫舍
• 53. 最大子数组和
• 322. 零钱兑换
• 300. 最长递增子序列

5.2 进阶挑战题

• 72. 编辑距离
• 115. 不同的子序列
• 132. 分割回文串II
• 174. 地下城游戏
• 312. 戳气球

5.3 面试高频题

• 5. 最长回文子串
• 10. 正则表达式匹配
• 32. 最长有效括号
• 139. 单词拆分
• 221. 最大正方形

6. 动态规划解题心得

1. 识别问题特征：当问题具有"最优子结构"和"重叠子问题"时，考虑动态规划解法。

2. 定义状态要明确：dp数组的定义直接影响状态转移方程的推导。常见定义方式包括：

   • dp[i]：以第i个元素结尾的某种最优解
   • dp[i][j]：涉及两个序列或两个维度的状态
   • dp[mask]：状态压缩表示

3. 边界条件很重要：初始条件处理不当是常见错误来源，特别是dp[0]、dp[1]等初始状态。

4. 画状态转移表：对于复杂问题，手动填写小规模例子的dp表能帮助理解状态转移逻辑。

5. 空间优化放在最后：先写出清晰的二维dp解法，确认正确后再考虑空间优化。

6. 注意遍历顺序：有些问题需要正向遍历，有些需要逆向遍历，这取决于状态依赖关系。

7. 调试技巧：打印dp表是调试动态规划问题的有效方法，可以直观看到状态转移是否正确。

动态规划的学习曲线较为陡峭，建议从简单问题入手，逐步建立解题直觉。每解决一个问题后，尝试用不同的状态定义重新思考，培养多角度分析问题的能力。