python 贪心-dfs-dp

内容分享1周前发布

0 0 0

贪心

一、什么是贪心算法？

一句话：

每一步都做“当前看来最优”的选择，不考虑将来，不回头改。

特点：

局部最优 → 期望得到全局最优

每一步选一个“看起来最划算”的选择；不像动态规划那样枚举所有子状态。

不回溯

一旦做了选择就不改了，所以实现上经常就是：

排序 + 一次线性扫描。

不是所有问题都适合贪心。
想用贪心，通常要满足两个性质：

贪心选择性质：
存在一种最优解，它的第一步就是我们贪心选的那个。最优子结构：
做了这步选择之后，剩下的子问题的最优解 + 当前选择 = 整体最优解。

二、例题 1：区间调度 / 活动选择（经典贪心）

题目描述

有 n 个活动，每个活动有开始时间 s[i] 和结束时间 e[i]，
一个人同一时间只能进行一个活动，问：最多能参加多少个活动？

例如：


活动编号:  1   2   3   4   5
开始时间:  1   3   0   5   8
结束时间:  4   5   6   7   9

常见错误思路（反例）

按 开始时间最早 排序选？不一定对。按 持续时间最短 排序选？也不一定对。

正确的贪心策略

按 结束时间从小到大排序，然后依次选择 能参加且结束最早 的活动。

理由直观一点说：

越早结束，就给后面的活动留的时间越多；不管你前面选择了哪个能够参加的活动，只要是“在最早结束时间之前结束”的，
换成“结束时间更早的那个”，一定不会让已经选的个数变少，后面只会更宽裕。

具体步骤

把所有活动按结束时间 e[i] 升序排序；

从头到尾扫一遍：

维护一个变量 last_end = 上一个被选中活动的结束时间；如果当前活动的开始时间 s[i] >= last_end，就选它，并更新 last_end = e[i]。

举例

活动：(start, end)


(1, 4), (3, 5), (0, 6), (5, 7), (8, 9)

按结束时间排序（其实已经是）：

选 (1,4)，last_end=4(3,5) 的 start=3 < last_end=4 → 冲突，跳过(0,6) 的 start=0 < 4 → 冲突，跳过(5,7) 的 start=5 ≥ 4 → 可以选，last_end=7(8,9) 的 start=8 ≥ 7 → 可以选

最后选了 3 个活动： (1,4), (5,7), (8,9)

Python 实现


from typing import List, Tuple

def max_activities(intervals: List[Tuple[int, int]]) -> int:
    # intervals: [(start, end), ...]
    # 1. 按结束时间排序
    intervals.sort(key=lambda x: x[1])

    count = 0
    last_end = float('-inf')

    # 2. 贪心地选结束最早且不冲突的活动
    for s, e in intervals:
        if s >= last_end:
            count += 1
            last_end = e

    return count

# 测试
intervals = [(1, 4), (3, 5), (0, 6), (5, 7), (8, 9)]
print(max_activities(intervals))  # 输出 3

这个问题是教科书级别的贪心成功案例：可以严格证明贪心的正确性。

三、例题 2：硬币找零（展示贪心何时不适用）

题目描述

给你几种硬币面值，比如：
中国常用的 [1, 2, 5, 10]，
问：给定一个金额 amount，用最少枚数凑出这个金额（假设一定能凑出来）。

贪心策略

每次都优先用 面值最大的硬币，能用几枚就用几枚，然后再考虑次大的，直到凑完。

在很多实际货币系统中（比如常见的 1,2,5,10…），这招是对的。

例如金额 18：

先用 10 → 剩 8再用 5 → 剩 3再用 2 → 剩 1再用 1 → 结束
总共 4 枚硬币。

Python 贪心写法


def coin_change_greedy(coins, amount):
    coins.sort(reverse=True)  # 从大到小
    count = 0
    for coin in coins:
        if amount == 0:
            break
        # 该面值最多能用多少枚
        use = amount // coin
        count += use
        amount -= use * coin
    return count if amount == 0 else -1  # -1 表示无法凑出

但贪心不总是对的：反例

设计一种面额系统：coins = [1, 3, 4]，amount = 6。

贪心：

先用 4 → 剩 2再用 1 → 剩 1再用 1 → 剩 0
→ 一共 3 枚（4 + 1 + 1）

但最优解：

用两枚 3：3 + 3 = 6
→ 只需要 2 枚！

这里贪心就错了，因为“每次拿最大面值”这个局部最优，并不能保证全局最优。

这道题如果面额任意给出，一般要用 动态规划 才能保证正确。

四、小结：怎么判断一个问题能不能用贪心？

一个比较实用的经验：

首先大胆想一个“看起来很自然”的贪心策略：

比如：最早结束、最小权重、最大价值密度、最短时间、最小消耗……

然后尝试：

造反例：看是否能构造一个数据，使得贪心得到的结果明显不是最优；

如果很难造反例，再尝试用“交换论证”证明：

假设存在一个最优解不是从贪心选择开始；然后一步一步把它“交换”成以贪心选择开头的另一组解，且不变差；得出：存在最优解以贪心选择开头 → 贪心策略是安全的。

深度优先

一、DFS 是什么？

核心一句话：

沿着一条路一直走到走不动，再回头换下一条路。

特点：

先走深，再回头（和 BFS 的“按层走”相反）

常用实现方式：

递归（函数自己调用自己）显式栈（stack.append() / stack.pop()）

典型应用场景：

图 / 树的遍历（搜索路径、连通块）迷宫寻路回溯类题（组合、排列、n 皇后，其实本质也是 DFS）

二、例题 1：图的遍历（DFS 输出访问顺序）

题目描述

给你一个无向图，用邻接表表示。
从某个起点 start 出发，用 DFS 输出访问节点的顺序。

例如图：


1 -- 2 -- 3
|    |
4 -- 5

邻接表可能写成：


graph = {
    1: [2, 4],
    2: [1, 3, 5],
    3: [2],
    4: [1, 5],
    5: [2, 4]
}

递归版 DFS


def dfs_recursive(graph, start, visited=None):
    if visited is None:
        visited = set()

    visited.add(start)
    print(start, end=' ')   # 这里就是“访问”这个点，你也可以做别的事

    for nei in graph[start]:
        if nei not in visited:
            dfs_recursive(graph, nei, visited)

# 测试
graph = {
    1: [2, 4],
    2: [1, 3, 5],
    3: [2],
    4: [1, 5],
    5: [2, 4]
}
dfs_recursive(graph, 1)   # 一种可能输出：1 2 3 5 4

执行过程（直观理解）：

从 1 出发 → 走 2 → 再走 3，3 没路了回退 → 回到 2，再走 5 → 再走 4……每次“走到没路为止，再退回上一个点”，非常符合“深度优先”。

非递归（显式栈）版 DFS


def dfs_stack(graph, start):
    visited = set()
    stack = [start]   # 用列表模拟栈

    while stack:
        node = stack.pop()   # 取栈顶
        if node in visited:
            continue
        visited.add(node)
        print(node, end=' ')

        # 把邻居压栈（可以反向压栈以控制访问顺序）
        for nei in reversed(graph[node]):
            if nei not in visited:
                stack.append(nei)

# 测试
dfs_stack(graph, 1)

三、例题 2：网格 DFS —— 岛屿数量 (Number of Islands)

这是力扣非常经典的一题，DFS 的标准应用。

题目描述（简化版）

给一个由 '1' 和 '0' 组成的二维网格，

'1' 表示陆地'0' 表示海水
上、下、左、右相邻的 '1' 视为同一块岛屿。

求：岛屿的数量。

示例：


grid =
1 1 0 0
1 0 0 1
0 0 1 1

这里有 3 个岛：
- 左上角 2×2 那块连在一起算 1 个岛
- 中间 (2,2) 单独一个岛
- 右下角 2 个 1 连在一起算 1 个岛

解题思路（用 DFS “淹没岛屿”）

扫描整个网格，每发现一个没有访问过的 '1'：

岛屿计数 +1从这个点出发做 DFS，把这个岛上所有相连的 '1' 都标记为已访问（或者直接改成 '0'，表示“淹掉”）

这样，后面再遇到这个岛上的格子就不会重复计数了。

递归 DFS 版本（Python）


from typing import List

def num_islands(grid: List[List[str]]) -> int:
    if not grid:
        return 0

    rows, cols = len(grid), len(grid[0])

    def dfs(r: int, c: int):
        # 越界或遇到水就停止
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return
        if grid[r][c] == '0':
            return

        # 将当前陆地标记为“水”，避免重复访问
        grid[r][c] = '0'

        # 向四个方向继续 DFS
        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


# 测试
g = [
    list("1100"),
    list("1001"),
    list("0011")
]
print(num_islands(g))  # 输出 3

这里 DFS 的角色：

把“从某个点连出去的整块连通区域”全部走一遍（并标记）；这就是 DFS 在“连通块计数”里的经典作用。

四、DFS 与回溯的关系（顺便一嘴）

你前面问过 n 皇后、回溯，其实：

回溯搜索 = 一种 带状态记录和恢复 的 DFS。

DFS 是“遍历图/树”的一般套路；回溯是在 DFS 上加了“试探 + 撤销”（比如试着放一个皇后、不行再拿掉）的逻辑。

五、小结

DFS 的核心：沿着一个方向走到头 → 回退 → 换方向。

通常用递归实现最自然，也可以手写栈。

典型题型：

图遍历、强连通分量、拓扑排序辅助树的先序/后序遍历网格搜索（岛屿数量、迷宫、连通块）各种回溯题（组合、排列、数独、n 皇后…）
下面按你指定的风格（是什么 → 解题思路 → 例题 → 总结）来系统讲 BFS（广度优先搜索）。
结构与你给的 DFS 模板完全一致，可直接作为笔记使用。

广度优先

一、BFS 是什么？

BFS（Breadth-First Search）是一种 按“层”遍历图/树的搜索方法：

先访问距离起点最近的节点再访问下一层更远的节点再下一层……

使用 队列（queue）先进先出 实现。

适合解决：

无权图最短路（最常考）找连通性层序遍历多源最短路判断二分图（染色层序）

图示：


1 -- 2 -- 3
|    |
4 -- 5

邻接表：


graph = {
    1: [2, 4],
    2: [1, 3, 5],
    3: [2],
    4: [1, 5],
    5: [2, 4]
}

二、BFS 模板（Python）

BFS 核心模板（单源最短路/层序遍历）


from collections import deque

def bfs(graph, start):
    visited = set()
    q = deque([start])
    visited.add(start)

    while q:
        node = q.popleft()
        print(node, end=' ')   # “访问”节点

        for nei in graph[node]:
            if nei not in visited:
                visited.add(nei)
                q.append(nei)

执行示例：


bfs(graph, 1)

可能输出：


1 2 4 3 5

执行顺序解释：

层级遍历：

距离 1 为 0 的：1距离 1 为 1 的：2、4距离 1 为 2 的：3、5

完全符合层序思想 → 这是 BFS 的特点。

三、例题 1：无权图最短路 BFS（最常考）

【题目】

输入 n, m（点数、边数），以及一张无向图。求从起点 s 到所有点的最短距离。

【示例输入】

【示例输出】


0 1 1 2 3

【解题思路】

BFS 按层遍历 → 第一次访问某点时的层号就是最短距离用 dist 数组记录距离，初始化为 -1

BFS 最短路代码


from collections import deque

n, m, s = map(int, input().split())
graph = [[] for _ in range(n+1)]

for _ in range(m):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

def bfs(start):
    dist = [-1] * (n + 1)
    dist[start] = 0
    q = deque([start])

    while q:
        u = q.popleft()
        for v in graph[u]:
            if dist[v] == -1:
                dist[v] = dist[u] + 1   # BFS：第一次到达即最短路
                q.append(v)
    return dist

ans = bfs(s)
print(*ans[1:])

四、例题 2：判断二分图（BFS 染色）

【题目】

给无向图，判断是否能用两种颜色染色，相邻节点不同色。（判断是否含奇环）

【示例】

三角形 → 不是二分图 → 输出 NO。

【解题思路】

BFS 按层染色，color[u] = 1 或 -1如果遇到邻居颜色一样 → 不合法

BFS 染色代码


from collections import deque

def is_bipartite(graph, n):
    color = [0] * (n+1)

    for start in range(1, n+1):
        if color[start] != 0:
            continue

        q = deque([start])
        color[start] = 1

        while q:
            u = q.popleft()
            for v in graph[u]:
                if color[v] == 0:
                    color[v] = -color[u]
                    q.append(v)
                elif color[v] == color[u]:
                    return False
    return True

五、例题 3：多源 BFS —— 网格中的最短距离

【题目】

给一个网格，里面若干个“源点”值为 1，其他为 0。
求每个格子到最近“源点”的距离。

示例网格：


1 0 0
0 0 0
0 0 1

输出：


0 1 2
1 2 1
2 1 0

【解题思路】

“多个起点同时入队” → 多源 BFS（非常常用）

多源 BFS 代码


from collections import deque

def multi_source_bfs(grid):
    R, C = len(grid), len(grid[0])
    q = deque()
    dist = [[-1]*C for _ in range(R)]

    # 全部源点入队
    for r in range(R):
        for c in range(C):
            if grid[r][c] == 1:
                dist[r][c] = 0
                q.append((r, c))

    dirs = [(1,0),(-1,0),(0,1),(0,-1)]

    while q:
        r, c = q.popleft()
        for dr, dc in dirs:
            nr, nc = r + dr, c + dc
            if 0 <= nr < R and 0 <= nc < C and dist[nr][nc] == -1:
                dist[nr][nc] = dist[r][c] + 1
                q.append((nr, nc))

    return dist

六、BFS 与 DFS 对比总结

特性	BFS	DFS
数据结构	队列	栈（隐式递归）
遍历顺序	按层扩散，先近后远	一条路走到底
最短路（无权图）	✔ 必须	✘ 不适合
找连通块	✔	✔
树的层序遍历	✔	✘
判断二分图	✔（按层染色）	✔
寻找路径	适合找最短路径	适合找所有路径（回溯）

七、小结（BFS 标准套路）

模板：

建图（邻接表）创建 queue初始化 dist / visited队列循环（pop → 遍历邻居 → push）根据题目做处理

关键特征：
BFS = 层序扩散 → 最短路天然满足。

动态规划

我直接用**“怎么想 + 两个经典例题 + Python 代码”**来讲动态规划（DP），看完你就能开始自己写简单 DP 题了。

一、动态规划是啥？

一句话版：

把大问题拆成小问题，小问题答案存起来，避免重复算，从而高效地得到最优解（或计数、最大值等）。

关键有两点：

重叠子问题：

同一个子问题会被反复计算，比如递归求 Fibonacci 时 f(30) 里会多次算 f(10)、f(11) ……DP 就是：算一次记下来，下次直接用。

最优子结构：

大问题的最优解可以由小问题的最优解组合出来。比如最长上升子序列长度，dp[i] 可以由前面 dp[j] 推出来。

写 DP 的套路一般是 5 步：

确定状态：dp[i] 表示什么？写转移方程：dp[i] 怎么由前面的状态转移来？初始化：起点的 dp 值是什么？遍历顺序：i 是从小到大还是反着，内外层循环谁在前？答案位置：最终答案是 dp[n] 还是 max(dp) 之类？

二、例题 1：爬楼梯（入门 DP）

题目

有一个楼梯一共 n 级台阶，每次你可以爬 1 级或者 2 级，问一共有多少种不同的爬法？

比如：

n = 1：只有 1 种（1）

n = 2：2 种（1+1，2）

n = 3：

1+1+11+22+1
→ 共 3 种

1. 状态定义

设 dp[i] 表示：爬到第 i 级台阶的不同走法数量。

2. 状态转移

走到第 i 级，有两种可能的“最后一步”：

倒数第二步在 i-1 级，这一步跨 1 级 → 从 dp[i-1] 转移来倒数第二步在 i-2 级，这一步跨 2 级 → 从 dp[i-2] 转移来

所以：

[
dp[i] = dp[i-1] + dp[i-2]
]

这其实和 Fibonacci 一样。

3. 初始化

dp[0] = 1（可以理解为在地面啥也不做只有 1 种）dp[1] = 1（只有迈一步）

4. 遍历顺序

i 从 2 往上算到 n：


for i in range(2, n+1):
    dp[i] = dp[i-1] + dp[i-2]

5. 答案

dp[n] 就是答案。

Python 实现


def climb_stairs(n: int) -> int:
    if n <= 1:
        return 1

    dp = [0] * (n + 1)
    dp[0] = 1
    dp[1] = 1

    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]

    return dp[n]

# 测试
print(climb_stairs(3))  # 3
print(climb_stairs(4))  # 5

你可以把 dp 数组打印出来看看每一项代表啥。

三、例题 2：0-1 背包问题（经典“最优值”DP）

题目（0-1 背包）

有 n 个物品，每个物品有：

体积 w[i]价值 v[i]

有一个容量为 W 的背包，每个物品最多选一次（要么不选，要么选一次），
问：在不超过容量 W 的前提下，能得到的最大价值是多少？

例子：


物品: i   1   2   3
体积w:    2   3   4
价值v:    4   5   6
背包容量 W = 5

可以选 1 + 2 号：体积 2+3=5，价值 4+5=9也可以选 1 + 3 号：体积 2+4=6 超了，不行也可以只选 3 号：体积 4，价值 6

所以最优是 9。

1. 状态定义

这里用比较标准的二维写法（更好理解）：

dp[i][j] 表示：在只考虑前 i 个物品、容量为 j 的情况下，所能得到的最大价值。

注意：i 表示物品数量，j 表示容量

2. 状态转移方程

对于第 i 个物品（下标从 1 开始记），有两种选择：

不选物品 i
那最大价值就是：不考虑 i 时的最大价值，
即 dp[i-1][j]选物品 i（前提：装得下，即 j >= w[i]）
那你就要占用 w[i] 的容量，得到 v[i] 的价值 + 背包剩余容量 j - w[i] 时前面 i-1 个物品的最大价值：
即 dp[i-1][j - w[i]] + v[i]

所以：

[
dp[i][j] = maxBig( dp[i-1][j], dp[i-1][j – w[i]] + v[i] Big)
]

当 j < w[i] 时，装不下，只能不选：

[
dp[i][j] = dp[i-1][j]
]

3. 初始化

dp[0][j] = 0：0 个物品时，无论容量多大，价值都是 0。dp[i][0] = 0：容量为 0，装不了东西。

4. 遍历顺序

外层 i: 从 1 到 n内层 j: 从 0 到 W


for i in range(1, n+1):
    for j in range(0, W+1):
        ...

5. 答案

dp[n][W] 就是答案：考虑所有 n 个物品，容量为 W 时的最大价值。

Python 实现（二维写法）


def knapsack_01(weights, values, W):
    """
    weights: 物品体积列表，比如 [2,3,4]
    values:  物品价值列表，比如 [4,5,6]
    W:       背包容量
    """
    n = len(weights)
    # dp[i][j]: 前 i 个物品、容量 j 时的最大价值
    dp = [[0] * (W + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        w = weights[i - 1]
        v = values[i - 1]
        for j in range(0, W + 1):
            # 不选第 i 个物品
            dp[i][j] = dp[i - 1][j]
            # 选第 i 个物品（前提是容量够）
            if j >= w:
                dp[i][j] = max(dp[i][j], dp[i - 1][j - w] + v)

    return dp[n][W]

# 测试
weights = [2, 3, 4]
values = [4, 5, 6]
W = 5
print(knapsack_01(weights, values, W))  # 输出 9

你也可以打印 dp 表，看“从左上往右下填表”的过程，更直观。