动态规划（Dynamic Programming，简称DP）是一种用于解决最优化问题的算法思想，适用于可以将问题分解为子问题，且子问题之间有重叠的情况。
🔍 一、什么是动态规划？
动态规划的核心思想是：
将原问题分解为子问题，先解决子问题并保存结果（记忆化），然后再组合这些子问题的解，从而得到原问题的解。
与分治算法的区别：
- 分治：子问题互不重叠；
- 动态规划：子问题重叠，因此可以通过保存子问题结果（记忆）来节省计算时间。
🧱 二、动态规划解题的五个步骤（套路）
1. 确定状态
找出问题可以由哪些子问题表示。
➡️ 通常是：“从前i个元素中…”、“背包容量为j时…”、“当前在(i, j)位置…”等。
2. 确定状态转移方程
即找到当前状态如何从其他状态转移过来。
3. 确定初始状态
通常是数组的第0位，或者空背包时的值。
4. 确定遍历顺序
根据依赖关系选择从前向后，或从后向前。
5. 返回结果
根据题意返回结果：可能是dp[n]、dp[n][m]、或是max(dp[i])等等。
✅ 三、Leetcode上的常见动态规划题型
| 类型 | 典型题目 | 简要描述 |
|---|---|---|
| 线性DP | 198. 打家劫舍 | 从一排房子中选不能相邻的最大收益 |
| 背包DP | 416. 分割等和子集 | 判断是否能分成和相等的两个子集 |
| 区间DP | 312. 戳气球 | 最优戳气球顺序 |
| 子序列DP | 300. 最长递增子序列 | 找出最长递增子序列 |
| 编辑距离 | 72. 编辑距离 | 最少操作使两个字符串相同 |
🧠 四、遇到动态规划题怎么做（实战指南）
比如你遇到一个LeetCode题目，看不出是不是DP，怎么办？
- 是否有“最值”（最大/最小）或者“方案数”？
- 如果是：可能适合DP。
- 例：“最多能抢多少钱”、“最少多少次操作”、“有多少种方法到终点”。
- 问题是否可以分解为子问题？
- 比如：“我只需要知道前i个的解，就能推出第i+1个”。
- 子问题是否重叠？
- 如果递归中重复计算了相同子问题，说明可以用DP优化。
📌 五、一个简单的例子：斐波那契数列
题目：fib(n)返回斐波那契数列第n项。
解法：
def fib(n):
if n <= 1:
return n
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
图论是计算机科学和离散数学中的一个重要分支，用于处理“节点（点）和它们之间的关系（边）”的问题。
🌐 一、什么是图论（Graph Theory）？
图（Graph）由两个基本元素组成：
- 节点（顶点）：比如城市、网页、用户等。
- 边：表示节点之间的连接关系，可能是有向或无向，有权重或无权重。
图的分类：
| 分类 | 说明 |
|---|---|
| 有向图 / 无向图 | 边是否有方向（如 A → B） |
| 有权图 / 无权图 | 边是否带权值（如路程/费用） |
| 稀疏图 / 稠密图 | 边的数量相对节点数量的多少 |
| 连通图 | 所有点之间是否都可以到达 |
🧰 二、图论常用算法
| 类型 | 算法 | 说明 |
|---|---|---|
| 遍历 | DFS / BFS | 深度优先 / 广度优先搜索 |
| 最短路径 | Dijkstra、Bellman-Ford、Floyd | 图中找最短路径 |
| 最小生成树 | Kruskal、Prim | 找连接所有点的最小总权值 |
| 拓扑排序 | Kahn 算法 / DFS | 解决有向无环图（DAG）中的顺序问题 |
| 联通性 | 并查集、Tarjan | 判断图是否连通或找强连通分量 |
| 染色 | 二分图 / 图着色 | 图能否被合理分组或染色 |
✅ 三、Leetcode 上的经典图论题目推荐
下面是一些难度和类型都有覆盖的题目：
🚶♂️ 遍历（BFS / DFS）
🛣️ 最短路径
🌉 并查集（Union Find）
⛓ 拓扑排序（DAG）
🧠 四、图论题目的常见分析套路
- 是否有路径/是否能到达？
- 用 BFS 或 DFS 遍历图。
- 求最短路径或最小代价？
- Dijkstra（无负权）、Bellman-Ford（有负权）或 A*。
- 求连通性 / 是否成环？
- 并查集、DFS 判断环。
- 图是有向无环图（DAG）？
- 拓扑排序能解决任务调度问题。
- 图不是明确的邻接表/邻接矩阵？
- 需要构建图结构，常用
defaultdict(list)或邻接矩阵构造。
📦 示例：Leetcode 200. 岛屿数量（DFS）
def numIslands(grid):
if not grid: return 0
rows, cols = len(grid), len(grid[0])
def dfs(r, c):
if r < 0 or c < 0 or r >= rows or c >= cols or grid[r][c] != '1':
return
grid[r][c] = '0' # 标记为已访问
dfs(r+1, c); dfs(r-1, c); dfs(r, c+1); dfs(r, c-1)
count = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == '1':
count += 1
dfs(r, c)
return count
Top comments (0)