跳至主要內容

大题

GGBOND2026/1/30大约 8 分钟

大题

第六章 动态规划

动态规划的设计思想

将要求解的较大规模的问题分割成若干个小规模的子问题。但是经分解得到的子问题往往不是互相独立的。如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，自底向上求解原问题的解。（关键词：分割大问题、不独立、自底向上）

某旅行商要访问4个城市A、B、C、D，城市间距离矩阵如下（单位：km）：

ABCD
A0101520
B1003525
C1535030
D2025300

从A出发最后回到A。请使用优先级队列式分支限界法（以当前路径长度+最小出边和作为下界）求最短路径，说明求解过程。

核心概念：

  • 下界 = 当前路径长度 + 剩余未访问城市的最小出边和，是当前路径扩展的理论最小值
  • 优先级队列：每次取出下界最小的节点扩展，优先处理最有希望的路径
  • 剪枝：若下界 ≥ 已知最优解（上界），则剪枝不再搜索该路径

最小出边：对于每个城市，最小出边是指该城市到其他所有城市的距离中最短的那

城市最小出边
A10
B10
C15
D20
总最小出边和 = 10 + 10 + 15 + 20 = 55

求解过程

  1. 初始
    路径 [A]，当前长度 0
    剩余未访问城市 {B,C,D}
    下界 = 0 + (10 + 15 + 20) = 45
    队列：[(45, [A])]

  2. 扩展 [A]

    • [A→B]：长度 10，下界 = 10 + (15 + 20) = 45
    • [A→C]：长度 15，下界 = 15 + (10 + 20) = 45
    • [A→D]：长度 20，下界 = 20 + (10 + 15) = 45
      队列：[(45,[A→B]), (45,[A→C]), (45,[A→D])]

  3. 扩展 [A→B]

    • [A→B→C]：长度 45，下界 = 45 + 20 = 65
    • [A→B→D]：长度 35，下界 = 35 + 15 = 50
      队列：[(45,[A→C]), (45,[A→D]), (50,[A→B→D]), (65,[A→B→C])]

  4. 扩展 [A→C]

    • [A→C→B]：长度 50，下界 = 50 + 20 = 70
    • [A→C→D]：长度 45，下界 = 45 + 10 = 55
      队列：[(45,[A→D]), (50,[A→B→D]), (55,[A→C→D]), (65,[A→B→C]), (70,[A→C→B])]

  5. 扩展 [A→D]

    • [A→D→B]：长度 45，下界 = 45 + 15 = 60
    • [A→D→C]：长度 50，下界 = 50 + 10 = 60
      队列：[(50,[A→B→D]), (55,[A→C→D]), (60,[A→D→B]), (60,[A→D→C]), (65,[A→B→C]), (70,[A→C→B])]

  6. 扩展 [A→B→D]
    完整路径：A→B→D→C→A
    总长度 = 10 + 25 + 30 + 15 = 80
    更新最优解 = 80

  7. 扩展 [A→C→D]
    完整路径：A→C→D→B→A
    总长度 = 15 + 30 + 25 + 10 = 80
    与当前最优解相同

其余节点虽下界小于 80，但继续扩展得到的完整回路长度均大于 80，因此不再更新最优解。

最终结果：
最短回路长度 80
最短回路：
A→B→D→C→A 或 A→C→D→B→A

给定一个包含n个整数的数组，其中有一个“主元素”出现次数超过n/2。请使用分治法设计算法找出该主元素，并说明求解过程。

算法设计：

  1. 分解：
    • 将数组 arr[left:right] 从中间位置 mid = (left + right) / 2 分成两个子数组：
    • 左子数组：arr[left:mid]
    • 右子数组：arr[mid+1:right]
  2. 递归：分别找出左右子数组的主元素（子数组可能没有主元素）
  3. 合并：
    • 若左右子数组都没有主元素，返回无主元素
    • 若只有一边有主元素，统计该元素在整个数组中的出现次数，判断是否超过n/2
    • 若两边主元素相同，直接返回该元素
    • 若两边主元素不同，分别统计两候选元素在整个数组中的出现次数，返回次数多的；若次数相同，返回无主元素

求解示例（数组：[2,2,1,1,1,2,2]）：

  1. 分解为：左[2,2,1]，右[1,1,2,2]
    • 左子数组递归分解→主元素为2（出现2次，超过3/2=1.5）
    • 右子数组递归分解→无主元素（1和2各出现2次，未超过4/2=2）
  2. 合并：
    • 左边有主元素2，右边无主元素
    • 统计2在整个数组中出现4次（超过n/2=3.5）→ 主元素为2

合并策略详解：

  • 为什么需要重新统计：子数组的主元素不一定是整个数组的主元素
    • 例如：数组[1,1,2,2,2]，左[1,1]主元素是1，但1在整个数组只出现2次（未超过5/2=2.5）
    • 必须在整个数组范围内统计才能确定真正的全局主元素
  • 次数相同的情况：若两个候选元素的出现次数相同，说明当前数组没有主元素
    • 例如：数组[1,1,2,2]，统计1和2都出现2次（未超过4/2=2），返回无主元素

时间复杂度：O(n log n)（递归深度log n，每层合并O(n)）
空间复杂度：O(log n)（递归栈深度）

贪心算法求解硬币找零问题

def coin_change_greedy(coins, amount):
    coins.sort(reverse=True)  # 从大到小排序
    result = []
    remaining = amount
    
    for coin in coins:
        while remaining >= coin:
            # 填空1：添加硬币到结果
            ______________
            # 填空2：更新剩余金额
            ______________
    
    return result if remaining == 0 else None

# 示例：coins=[25,10,5,1], amount=63

第1空：result.append(coin)
第2空：remaining -= coin

解析：

  1. 贪心算法基本思想：每次选择当前面值最大的硬币，尽可能多地使用，直到凑出目标金额。
  2. 代码执行流程：
    • 首先将硬币按从大到小排序
    • 遍历每个硬币，使用while循环尽可能多地取该面值硬币
    • 每次取硬币时，将其添加到结果列表，并更新剩余金额
  3. 示例运行：
    • coins=[25,10,5,1], amount=63
    • 25*2=50 → result=[25,25], remaining=13
    • 10*1=10 → result=[25,25,10], remaining=3
    • 5*0=0 → 跳过（3<5）
    • 1*3=3 → result=[25,25,10,1,1,1], remaining=0
  4. 返回结果：[25,25,10,1,1,1]，共6个硬币

核心知识点：贪心算法通过局部最优选择期望得到全局最优解，适用于具有贪心选择性质的问题。

递归排序（归并排序）

def merge_sort(arr, left, right):
    if left >= right:
        return
    mid = (left + right) // 2
    # 填空1：递归分解左半部分
    ______________
    # 填空2：递归分解右半部分
    ______________
    merge(arr, left, mid, right)  # 合并两个有序子数组

# 合并函数（辅助实现）
def merge(arr, left, mid, right):
    # 创建临时数组存储合并结果
    temp = [0] * (right - left + 1)
    i, j, k = left, mid + 1, 0
    # 合并两个有序子数组
    while i <= mid and j <= right:
        if arr[i] <= arr[j]:
            temp[k] = arr[i]
            i += 1
        else:
            temp[k] = arr[j]
            j += 1
        k += 1
    # 处理剩余元素
    while i <= mid:
        temp[k] = arr[i]
        i += 1
        k += 1
    while j <= right:
        temp[k] = arr[j]
        j += 1
        k += 1
    # 将临时数组复制回原数组
    for p in range(len(temp)):
        arr[left + p] = temp[p]

# 示例调用：merge_sort(arr, 0, len(arr)-1)

第1空：merge_sort(arr, left, mid)
第2空：merge_sort(arr, mid + 1, right)

解析：

  1. 归并排序基本思想：采用分治策略，将数组不断分为两半，递归排序后合并。
  2. 代码执行流程：
    • 递归终止条件：left >= right（子数组只有一个元素或为空）
    • 计算中间位置 mid
    • 递归排序左半部分 [left, mid]
    • 递归排序右半部分 [mid+1, right]
    • 调用 merge 函数合并两个有序子数组
  3. 分治过程：
    • 分解：将数组分为左右两部分
    • 解决：递归排序左右两部分
    • 合并：将排序后的左右两部分合并为一个有序数组
  4. 时间复杂度：O(n log n)，递归深度为 O(log n)，每层合并时间为 O(n)
  5. 空间复杂度：O(n)，需要额外空间存储合并结果

核心知识点：归并排序是分治策略的典型应用，通过递归分解和合并实现排序，具有稳定的时间复杂度。

回溯法求全排列问题

def permute(nums):
    def backtrack(path, used):
        if len(path) == len(nums):
            result.append(path[:])  # 保存一个完整排列
            return
        
        for i in range(len(nums)):
            if used[i]:  # 填空1：检查数字是否已使用
                ______________
            
            # 做选择
            path.append(nums[i])
            used[i] = True
            
            # 递归
            backtrack(path, used)
            
            # 撤销选择
            path.pop()
            # 填空2：恢复使用状态
            ______________
    
    result = []
    used = [False] * len(nums)
    backtrack([], used)
    return result

# 示例：nums=[1,2,3]

第1空：continue
第2空：used[i] = False

解析：

全排列问题：给定一个不含重复元素的数组，返回其所有可能的全排列。例如，对于数组 [1,2,3]，其全排列共有6种：

  • [1,2,3]
  • [1,3,2]
  • [2,1,3]
  • [2,3,1]
  • [3,1,2]
  • [3,2,1]

算法思路：使用回溯法深度优先搜索解空间树，每个节点代表一个部分排列，叶子节点代表完整排列。

  1. 回溯法基本思想：通过尝试所有可能的选择，搜索问题的解空间，当发现当前选择不可能得到解时，回溯到上一步，尝试其他选择。
  2. 代码执行流程：
    • 定义 backtrack 函数，接收当前路径 path 和已使用数字数组 used
    • 终止条件：当路径长度等于数组长度时，保存完整排列
    • 遍历所有数字：
      • 如果数字已使用，跳过（continue）
      • 做选择：将数字添加到路径，标记为已使用
      • 递归调用 backtrack 函数
      • 撤销选择：从路径中移除数字，恢复使用状态为未使用
  3. 解空间树：
    • 树的每一层代表选择一个位置上的数字
    • 每个节点代表一个部分排列
    • 叶子节点代表完整排列
  4. 示例运行：
    • 对于 nums=[1,2,3]，backtrack 函数会生成所有6种排列
  5. 时间复杂度：O(n!)，n为数字个数，共有n!种排列
  6. 空间复杂度：O(n)，递归深度为n，需要额外空间存储路径和使用状态

核心知识点：回溯法是一种试探性搜索算法，通过深度优先搜索解空间树，并在搜索过程中进行剪枝，以减少搜索空间。

Copyright © 2026 GGBOND