说明问题：输入、输出和步骤
写代码之前，先把问题准确地描述出来。这叫做问题说明。
- 输入：我们拿到什么数据，它的类型和范围是什么（例如“n个整数，1 ≤ n ≤ 1000”）。
- 输出：我们必须给出什么（例如“其中最大的数”）。
- 条件：开始前什么成立（前置条件），结束后什么成立（后置条件）。
写出步骤
算法是一串有限而清楚的步骤，能把任何合法的输入变成正确的输出。可以这样写：
- 自然语言：“看每一个数；如果它比目前最大的还大，就记住它。”
- 编号的步骤列表：1. best ← 第一个数。2. 对后面每个数 x：如果 x > best，就令 best ← x。3. 输出 best。
- 伪代码或流程图：更精确。
用小的输入手动试一试，也要试特殊情况（所有数都相等、有负数、只有一个数）。
自顶向下和自底向上设计
自顶向下（逐步求精）：从整个任务开始，先拆成几个大步骤，再把每个步骤继续拆，直到每一小块都容易写成代码。例如：“做成绩单”→ 读入分数 → 计算平均分 → 评定等级 → 打印。
自底向上：先做好并测试小的、可重复使用的零件（比如求最大值的函数、排序的函数），再把它们拼成完整的程序。
真正的项目两种都用：自顶向下做计划，自底向上来制作和测试。
分治法和对半查找
分治有三步：把问题拆成同类的更小部分，解决每一部分（常常用递归），再把答案合并。
- 二分查找（对半）：在排好序的列表里，和中间的数比较，扔掉一半。n个数大约要查 log₂ n 次：16 → 4，1 000 000 → 20。
- 归并排序：把列表分成两半，各自排序，再合并：O(n log n)。
- 快速幂：a⁸ = ((a²)²)²：只要3次乘法，而不是7次。
- 二分法求根：把函数值变号的区间不断对半缩小。
贪心算法
贪心算法每次选当下看起来最好的，而且选了就不再改。
- 用 50、20、10、5、2、1 的硬币找零：先拿最大的硬币。对这样的硬币组合，结果是最优的。
- 一天里想参加最多的活动：每次都选最早结束的那个。这是最优的。
- 分数背包：先拿每千克价值最高的物品。这是最优的。
但贪心不一定正确：硬币是 1、3、4 时，用贪心付 6 会得到 4 + 1 + 1（3枚），而 3 + 3 只要 2 枚。要相信一个贪心方法，必须证明它，或者拿它和一定正确的方法对比测试。
动态规划和回溯
动态规划（DP）
当同样的小问题反复出现时，每个只解一次，把答案存进表里。凑出金额 a 的最少硬币数：best[a] = 1 + min(best[a - c])，对所有 c ≤ a 的硬币 c 取最小，从 best[0] = 0 开始。硬币为 1、3、4 时：best = 0, 1, 2, 1, 1, 2, 2。从小到大填表是自底向上；带记忆的递归是自顶向下（记忆化）。更多内容见单独的动态规划课程。
回溯
一次做一个选择来构造解。如果某个选择违反规则或走进死路，就撤销它，再试下一个选项。可以用于迷宫、数独、N皇后问题和列出所有子集。它是一种小心的暴力法：会跳过所有不可能成功的整条分支。
暴力法
把每一种可能的答案都试一遍。总是正确，但往往慢得无法接受（2ⁿ 个子集，n! 种排列）。
选择方法：正确性、效率和数据结构
| 方法 | 适合的情况 | 例子 | 常见时间 |
|---|---|---|---|
| 暴力法 | 输入很小 | 试遍3位数的所有密码 | 常常是 2ⁿ 或 n! |
| 分治 | 各部分互相独立 | 二分查找、归并排序 | O(log n)、O(n log n) |
| 贪心 | 已证明局部最优选择是安全的 | 活动选择、找零 | O(n log n) |
| 动态规划 | 小问题会重复 | 硬币找零、最短路径 | 表的大小 |
| 回溯 | 带规则的搜索 | 迷宫、数独 | 指数级，但会剪枝 |
要说明理由
正确性：说明算法一定会停下来，并给出正确的输出（用循环不变式、证明，或者对边界情况的测试）。效率：数一数当 n 变大时步数怎么增长（大O），并和其他方法比较。
数据结构来帮忙
数组用来做表（动态规划），栈用来做回溯（记住该退回到哪里），队列用来一层一层地搜索。二叉树存放数据时，每个结点最多有两个孩子；在二叉搜索树里，较小的键放左边，较大的放右边，所以每往下一层，查找的工作就减半，就像二分查找一样。
动手试试：硬币和猜数游戏
- 和朋友玩1到100的猜数游戏。每次都问中间的数。你能保证7次以内猜中吗？（2⁷ = 128。）
- 硬币为 1、3、4，在纸上写出金额0到10的动态规划表。贪心在哪里出错？
- 打开最后一个3D步骤。试试硬币 1、7、10，金额 14。贪心给出 10 + 1 + 1 + 1 + 1；动态规划给出 7 + 7。
- 为“找出列表中最小的数”写一个步骤列表，并用 5, 5, 5 和只有一个数的情况来测试。
重点公式和概念
- 说明 = 输入 + 输出 + 条件
- 对半：大约 log₂ n 步（16 → 4，1024 → 10）
- 硬币DP：best[0] = 0；best[a] = 1 + min best[a - c]
- 分治 = 拆开 + 解决 + 合并
- 贪心很快，但必须证明它是最优的
例题讲解
1. 为“找出n个数中最大的数”写出问题说明和步骤列表。
输入：n ≥ 1 个数。输出：最大的那个数。步骤：1. best ← 第一个数。2. 对其他每个数 x：如果 x > best，就令 best ← x。3. 输出 best。对于 4, 9, 2, 7, 12, 5, 10, 3，比较7次后输出 12。
2. 要在1到1000中找出一个数，对半查找需要问几个问题？
每个问题都把范围减半：1000 → 500 → 250 → 125 → 63 → 32 → 16 → 8 → 4 → 2 → 1。一共10个问题（2¹⁰ = 1024 ≥ 1000）。
3. 用 50、20、10、5、2、1 的硬币，按贪心方法付 87。
50（剩 37），20（剩 17），10（剩 7），5（剩 2），2（剩 0）：50 + 20 + 10 + 5 + 2 = 5 枚硬币。
4. 硬币为 1、3、4，填出金额到 7 的DP表。
best[0]=0，[1]=1，[2]=2，[3]=1，[4]=1，[5]=min(best4, best2, best1)+1=2，[6]=min(best5, best3, best2)+1=2，[7]=min(best6, best4, best3)+1=2（3 + 4）。
5. 活动（开始-结束）：A 9-11，B 10-12，C 11-13，D 12-14，E 13-15。选出互不重叠、数量最多的活动。
按最早结束的贪心：A（11结束），然后 C（11开始，13结束），再选 E（13开始）。共3个活动：A、C、E。
6. 用自顶向下的方法设计：一个告诉全班平均分和最高分同学的程序。
第1层：读入数据 → 计算 → 打印。第2层：把姓名和分数读入列表；计算总分和平均分；找出最高分及其姓名；打印两者。然后每一块自底向上地编写和测试。
常见错误
- 没说清输入和输出就开始写代码。很多“错误”其实是说明不清楚造成的。
- 以为贪心总是最优。只有能证明时才行（硬币 1、3、4 就会让它出错）。
- 对没有排序的列表用二分查找。对半查找需要有序的数据。
- 把动态规划和分治混为一谈。动态规划用于要存起来的重叠子问题；分治是拆成互相独立的部分。