算法讲解066 必备 从递归入手一维动态规划

来源：算法讲解066【必备】从递归入手一维动态规划　·　2026-10-31

依据：无字幕，部分内容由我补充（已标注）

一句话概括

一维动态规划（1D Dynamic Programming）就是把「大问题」拆成「只依赖前面若干个位置的小问题」，用数组 dp[i] 记录「以 i 结尾 / 前 i 个元素」的最优值，按 i 从小到大递推，每个状态只花 O(1)（有时 O(k)）转移。

它解决什么问题

• 求「前 i 个元素」的最优值：最大子段和、最长上升子序列（LIS）、打家劫舍、爬楼梯、斐波那契类计数。
• 求「以 i 结尾」的最优值：最大子数组、股票买卖、粉刷栅栏、解码方法。
• 计数类：方案数、路径数、括号匹配数（Catalan 的一维形式）。
• 判定类：能否拆分、能否跳跃到终点（Jump Game）。

核心特征：状态是一维的，转移只依赖 dp[i-1]、dp[i-2] 或 dp[j] (j<i)，不涉及二维区间。

基础知识（前置概念，用大白话解释）

• 递归（Recursion）：函数自己调自己。写 f(n) = f(n-1) + f(n-2) 就是递归。
• 记忆化（Memoization）：递归会重复算同一个子问题，用一个数组 memo[] 存下来，算过就直接返回。这是「自顶向下」的 DP。
• 递推（Iteration / Bottom-up）：反过来，从最小的问题开始，dp[0], dp[1], ... 一路算到 dp[n]。这是「自底向上」的 DP，也就是通常说的一维 DP。
• 状态（State）：dp[i] 表示什么。定义错了后面全错。
• 转移方程（Transition）：dp[i] 怎么由前面的 dp 推出来。
• 边界（Base case）：dp[0]、dp[1] 这种最小规模的值，必须手动初始化。
• 无后效性（No aftereffect）：dp[i] 一旦算出来，后面不会再改它，也不依赖「怎么走到 i 的」，只依赖数值本身。

原理（为什么这么做是对的，尽量给直觉）

以斐波那契为例：f(n) = f(n-1) + f(n-2)。直接递归的调用树是指数级的，因为 f(n-2) 会被算很多遍。

关键观察：f(k) 只由 k 决定，跟「谁调用它」无关。所以算一次存起来，之后 O(1) 取用。

为什么从小到大填表是对的：转移方程里 dp[i] 只依赖下标比 i 小的项，那么按 i 递增的顺序填，填到 dp[i] 时它依赖的项一定已经填好了。这就是拓扑序（Topological Order）——一维下标天然就是拓扑序。

为什么可以滚动数组：如果 dp[i] 只依赖 dp[i-1] 和 dp[i-2]，那更早的值永远用不到了，两个变量 prev2, prev1 就够，空间从 O(n) 降到 O(1)。

直觉总结：DP = 递归 + 不重复算 + 按依赖顺序算。一维 DP 就是「依赖顺序恰好是下标顺序」的最简单情形。

步骤（编号，可照着写）

1. 定义状态：明确 dp[i] 的含义（「前 i 个」还是「以 i 结尾」，两者转移完全不同）。
2. 写转移方程：从「最后一步」倒推——dp[i] 由哪些 dp[j] (j<i) 转移来，取 max/min/sum。
3. 定边界：dp[0]、dp[1] 手动赋值；注意下标从 0 还是 1 开始。
4. 定遍历顺序：一般 for i = 1..n，内层若需枚举 j 则 for j = 0..i-1。
5. 定答案：是 dp[n] 还是 max(dp[0..n])（「以 i 结尾」型通常要取全局 max）。
6. 优化（可选）：能滚动就滚动；转移是「前缀 max/min」就用变量维护；LIS 用二分。
7. 多测清空：每组数据重新初始化 dp 数组（或 fill）。

样例（一个具体小例子，带每步变化）

最大子段和：a = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

定义 dp[i] = 以 a[i] 结尾的最大子段和。

转移：dp[i] = max(a[i], dp[i-1] + a[i])。

答案：max(dp[0..n-1])。

| i | a[i] | dp[i-1]+a[i] | dp[i] | 当前全局 max |

|---|------|--------------|-------|--------------|

| 0 | -2 | — | -2 | -2 |

| 1 | 1 | -1 | 1 | 1 |

| 2 | -3 | -2 | -2 | 1 |

| 3 | 4 | 2 | 4 | 4 |

| 4 | -1 | 3 | 3 | 4 |

| 5 | 2 | 5 | 5 | 5 |

| 6 | 1 | 6 | 6 | 6 |

| 7 | -5 | 1 | 1 | 6 |

| 8 | 4 | 5 | 5 | 6 |

答案 = 6（子段 [4,-1,2,1]）。

代码（Python 一份：好读、用于理解；C++ 一份：竞赛风，能直接抄进比赛，带注释，不用玄学宏）

Python（最大子段和，好读版）

def max_subarray(a):
    n = len(a)
    if n == 0:
        return 0
    dp = [0] * n
    dp[0] = a[0]
    ans = dp[0]
    for i in range(1, n):
        dp[i] = max(a[i], dp[i - 1] + a[i])
        ans = max(ans, dp[i])
    return ans

# 滚动数组版
def max_subarray_roll(a):
    prev = a[0]
    ans = a[0]
    for x in a[1:]:
        prev = max(x, prev + x)
        ans = max(ans, prev)
    return ans

C++（竞赛风，最大子段和，滚动数组）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<long long> a(n);
    for (auto &x : a) cin >> x;

    long long prev = a[0];   // dp[i-1]
    long long ans  = a[0];   // 全局最大
    for (int i = 1; i < n; ++i) {
        prev = max(a[i], prev + a[i]);  // dp[i] = max(a[i], dp[i-1]+a[i])
        ans  = max(ans, prev);
    }
    cout << ans << '\n';
    return 0;
}

复杂度（时间/空间，最好/平均/最坏，顺带说常数大不大）

• 时间：O(n)（转移 O(1) 的情形）；若内层枚举 j 则 O(n²)（如朴素 LIS）。
• 空间：O(n) 存 dp；滚动数组后 O(1)。
• 常数：极小，一维 DP 是最快的 DP 形式，1e7 级别数据都能过。LIS 二分版 O(n log n)，常数也小。

竞赛里什么时候用（看到什么题面特征就该想到它）

• 「前 i 个元素」「以 i 结尾」的最优值/方案数。
• 序列上做选择，相邻元素有约束（不能同时选、必须间隔 k）。
• 计数：爬楼梯、解码方法、粉刷栅栏、不同路径（一维压缩后）。
• 判定可达性：Jump Game、能否拆分单词。
• 数据规模 n ≤ 1e5~1e6，且答案是「线性扫描一遍能维护」的形式。
• 出现「最大子段和」「最长上升子序列」「打家劫舍」这类经典模型。

竞赛模板（C++，可直接背下来的写法；变量名清楚）

模板 1：最大子段和（滚动）

// 输入 n 和数组 a，输出最大子段和（至少选一个元素）
long long maxSubarray(const vector<long long>& a) {
    long long prev = a[0], ans = a[0];
    for (int i = 1; i < (int)a.size(); ++i) {
        prev = max(a[i], prev + a[i]);
        ans  = max(ans, prev);
    }
    return ans;
}

模板 2：最长上升子序列 LIS（O(n log n)，严格上升）

// 返回 LIS 长度；tails[k] = 长度为 k+1 的上升子序列的最小结尾
int lisLength(const vector<int>& a) {
    vector<int> tails;
    for (int x : a) {
        auto it = lower_bound(tails.begin(), tails.end(), x); // 严格上升用 lower_bound
        if (it == tails.end()) tails.push_back(x);
        else *it = x;
    }
    return (int)tails.size();
}
// 非严格上升（允许相等）把 lower_bound 换成 upper_bound

模板 3：打家劫舍（不能选相邻）

// dp[i] = max(dp[i-1], dp[i-2] + a[i])
long long rob(const vector<long long>& a) {
    long long prev2 = 0, prev1 = 0;   // dp[i-2], dp[i-1]
    for (long long x : a) {
        long long cur = max(prev1, prev2 + x);
        prev2 = prev1;
        prev1 = cur;
    }
    return prev1;
}

模板 4：解码方法（计数，取模）

const int MOD = 1'000'000'007;
// s 为数字串，返回解码方案数
int numDecodings(const string& s) {
    int n = (int)s.size();
    vector<long long> dp(n + 1, 0);
    dp[0] = 1;
    dp[1] = (s[0] != '0') ? 1 : 0;
    for (int i = 2; i <= n; ++i) {
        if (s[i - 1] != '0') dp[i] = (dp[i] + dp[i - 1]) % MOD;
        int two = (s[i - 2] - '0') * 10 + (s[i - 1] - '0');
        if (two >= 10 && two <= 26) dp[i] = (dp[i] + dp[i - 2]) % MOD;
    }
    return (int)dp[n];
}

边界与易错点（WA 的常见原因，越具体越好）

1. 状态定义混淆：「前 i 个」和「以 i 结尾」是两套转移，答案取法也不同（后者通常要 max(dp[0..n-1])，不是 dp[n-1]）。
2. 下标从 0 还是 1：dp 开 n+1 用 1-based 更省心；开 n 用 0-based 时注意 dp[0] 是边界。
3. 空输入 / n=0：最大子段和、LIS 等要特判，否则 a[0] 越界。
4. 全负数：最大子段和不能初始化为 0，否则全负数组返回 0（错）。初始化为 a[0] 或 -INF。
5. long long：答案可能超 int（如方案数、和），dp 用 long long，取模前别溢出。
6. 取模：加法取模每次加完就 %；减法取模要 (x % MOD + MOD) % MOD。
7. 多测清空：vector 重新构造或 fill(dp.begin(), dp.end(), 0)；别忘清 ans。
8. LIS 严格 vs 非严格：lower_bound 严格上升，upper_bound 非严格，写反直接 WA。
9. 滚动数组顺序：prev2 = prev1; prev1 = cur; 顺序写反就错，先更新 prev2 再更新 prev1。
10. 转移方向：0/1 背包类一维压缩必须倒序枚举容量，完全背包正序——一维 DP 最容易在这里翻车。

同类题 / 变形（说清楚怎么改）

• 最大子段和 → 最大子段积：要同时维护 max 和 min（负数乘负数变正），dpMax[i], dpMin[i] 两个一维数组。
• 最大子段和 → 环形数组：答案 = max(普通最大子段和, 总和 - 最小子段和)，注意全负特判。
• LIS → 最长不下降：lower_bound 改 upper_bound。
• LIS → 最长下降：把数组取反或反向比较。
• 打家劫舍 → 环形：首尾不能同时选，分「选首不选尾」「选尾不选首」两次跑。
• 打家劫舍 → 树形：变成树上 DP（树形 DP 的入门）。
• 爬楼梯 → 每次可走 1..k 步：dp[i] = sum(dp[i-1..i-k])，用前缀和/滑动窗口优化到 O(n)。
• **解码方法 → 带 * 通配**：多分支讨论，仍是 O(n) 一维。
• Jump Game → 最少跳跃次数：dp[i] = 到 i 的最少步数，或贪心 BFS 层数。

常见坑

• 把「以 i 结尾」的 dp 直接输出 dp[n-1]，忘了取全局 max。
• 初始化 dp[0] 时没考虑题目是否允许「空段」（允许空段才初始化为 0）。
• LIS 的 tails 数组不是真正的 LIS，只是长度对，别拿它还原序列（要还原得存前驱）。
• 多测时 vector<int> dp(n+1) 每次重建没问题，但全局数组忘了 memset。
• 用 int 存方案数，中途溢出再取模，结果错。
• 滚动数组变量更新顺序写反。
• 一维压缩背包正序/倒序搞混。

拓展（变体、实际用途、面试常问）

• 自顶向下 vs 自底向上：记忆化搜索写起来直观（尤其状态转移带条件分支时），递推常数小、无递归栈风险。竞赛里状态简单就递推，状态复杂先写记忆化再考虑改递推。
• 状态压缩：一维 DP 的「滚动」本质是状态压缩的雏形；二维压一维（背包）、状压 DP（bitmask）都是它的延伸。
• 实际用途：语音识别（Viterbi 一维链）、生物序列比对（编辑距离的一维压缩）、金融里的最大回撤（最大子段和的变体）。
• 面试常问：爬楼梯、打家劫舍、最大子序和、LIS、买卖股票的最佳时机（I/II/含冷冻期）——全是一维 DP 家族。

自测 3 题（题目 + 折叠答案）

题 1：给长度 n 的数组 a（可正可负），求最大子段和，要求子段非空。n ≤ 1e6，|a[i]| ≤ 1e9。