14.3.1 算法策略知识点概述

算法策略题通常不是让你写完整算法，而是判断“这个问题使用了哪种思想”。软考常见四类：分治、贪心、动态规划、回溯。

四种策略总览

策略	核心思想	关键词
分治法	把问题分成规模更小、相互独立的子问题，再合并	二分、递归、分解合并
贪心法	每一步选择当前最优，希望得到整体最优	当前最优、最小边、最短、最大收益
动态规划	保存重叠子问题结果，通过状态转移求最优	最优子结构、递推式、填表
回溯法	在解空间中尝试，失败则撤销选择	试探、剪枝、回退、所有解

识别策略的第一反应

flowchart TD
  A["读题干"] --> B{"是否明显分成若干独立子问题？"}
  B -->|是| C["分治"]
  B -->|否| D{"是否每步选当前最优？"}
  D -->|是| E["贪心"]
  D -->|否| F{"是否有递推式/填表/重叠子问题？"}
  F -->|是| G["动态规划"]
  F -->|否| H{"是否尝试所有可能并回退？"}
  H -->|是| I["回溯"]

本节例题

单选

题干出现“最优子结构、递推式、用数组保存子问题解并填表”，最可能使用的算法策略是：

A分治法B贪心法C动态规划法D回溯法

自查清单

1. 能否用一句话区分四种策略？
2. 能否识别“填表”通常对应动态规划？
3. 能否识别“失败撤销选择”通常对应回溯？