选或不选，推出最优子结构
这一课只练一件事：遇到“不能选相邻两个位置、要最大化总和”这类问题时，用 dp[i] 表示到第 i 个位置为止能拿到的最大总和，用写出转移式子，并确认这是而不是靠感觉贪心。必会：能列出状态表、能写出转移式子、能检查不可达状态（比如 i-2 不存在时不能越界读取，要按已给的初值处理）。最小示例：4 个位置的金额 3 7 4 6，规则是不能选相邻两个位置，求能拿到的最大总和，1 <= n <= 1000。样例追踪：dp[0] = 3，dp[1] = max(3, 7) = 7，dp[2] = max(dp[1], dp[0]+4) = max(7, 7) = 7，dp[3] = max(dp[2], dp[1]+6) = max(7, 13) = 13，所以 dp[3] = 13。边界是 n=1（只有一个位置，直接选它）和不可达状态（i-2 越界时不能凭空访问，要靠 dp[0]、dp[1] 的初值兜底）。建议掌握：这比枚举所有选法（2 的 n 次方种）快得多，n 变大时只有枚举才会超时。拓展：如果 dp[i] 只依赖前两个状态，可以用把整个数组换成两个变量，现在只需要认识这个概念，不强制要求会写。这里不会在浏览器里运行 C++。
任务 1：先选出该怎么定义状态
先用一句话确定 dp[i] 的含义，再确定第 i 个位置该怎么。点不认识的词可看基础解释。
必会：能说出 dp[i] 表示前 i 个位置（不选相邻）能拿到的最大金额；能说出第 i 个位置只有“选它”和“跳过它”两种情况，取较大值。这里不会在浏览器里运行 C++，只练习选择和走过程。
4 个位置的金额 3 7 4 6，不能选相邻两个位置，要求最大总和，该怎么定义状态最合适？状态定义 · 必会
确定用 dp[i] 表示前 i 个位置的最优解后，第 i 个位置该怎么决策？选或不选 · 必会
任务 2：按状态、初始化、转移三步推出 dp 表
最小示例：4 个位置的金额 3 7 4 6，不能选相邻两个位置。按顺序点三步：先写定义，再写，最后用推到 dp[3]。这里不会在浏览器里运行 C++。
必会：能解释每一步为什么这样做。边界：不要跳过“转移”直接猜答案；转移时 i-2 越界（比如 i=0、i=1）不能凭空读取，要靠 dp[0]、dp[1] 的初值兜底，不能读到不存在的格子。
- // 状态：dp[i] 表示考虑前 i 个位置（不选相邻）能拿到的最大金额
- // 初始化：dp[0] = 3，dp[1] = max(3, 7) = 7
- // 转移：dp[i] = max(dp[i-1], dp[i-2] + nums[i])
- // dp[2] = max(7, 3+4) = 7；dp[3] = max(7, 7+6) = 13
三步走完了，现在把 dp 表的推导落成一行代码：位置 i 只有两种可能—— 它，两种里取金额更大的那个。下面是只读脚手架，只留一空给你敲键盘；这里不会在浏览器里运行 C++。
- // nums 是每个位置的金额，dp[i] 是考虑前 i 个位置能拿到的最大金额
- int dp[100005];
- dp[0] = nums[0]; // 初始化：只有一个位置时只能选它
- dp[1] = max(nums[0], nums[1]); // 初始化：前两个位置只能选其中一个
- for (int i = 2; i < n; i += 1) {
- // 不选 i，或者选 i 再接上 i - 2 的结果
- }
- cout << dp[n - 1];
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]); // 不选 i 就沿用 dp[i - 1]；选 i 就不能选 i - 1，要接 i - 2
任务 3：确定处理思路，并认出两个边界
建议掌握：这题也能枚举所有选法（每个位置选或不选，共 2 的 n 次方种），但 n 变大时枚举会超时；用 dp 表按状态推导，复杂度大约是 O(n)，能覆盖常见测试点。拓展：如果 dp[i] 只依赖 dp[i-1] 和 dp[i-2]，可以用状态压缩把数组换成两个变量，现在只用认识这个概念。
必会 / 建议掌握 / 拓展：必会是列出状态表、写出转移式子、检查不可达状态。建议掌握是 DP 比枚举所有选法快得多。状态压缩是拓展，现在不用当硬门槛。
- // 思路：dp[i] = max(dp[i-1], dp[i-2] + nums[i])，从小到大递推
- // 边界 1：n=1 时只有一个位置，dp[0] = nums[0] 就是答案
- // 边界 2：i-2 越界（i=0、i=1）时不能凭空访问，靠 dp[0]、dp[1] 的初值兜底
- // 状态压缩（只用两个变量代替整个数组）是拓展
先选出这题该用什么处理思路：
再选出两个边界：
任务 4：随机小测，看看你是否真的懂了
每次从本课题库抽出三道不同的选择题。题目与解析已通过校验，答完后看解析，不要只看分数；拿不准就回到对应任务再看一遍。