线性动态规划基础详解：4 道经典例题与优化技巧

时间复杂度分析

基础版的时间复杂度是 O(N*K)。当 N=1e5、K=100 时，总运算量是 1e7，可以通过。但如果 K 更大，会超时。

优化技巧：前缀和优化（O(N) 复杂度）

观察状态转移方程，dp[i] 是前 K 个状态的和。我们可以用一个前缀和数组 sum[i] 表示 dp[0]~dp[i] 的和，将求和转化为 O(1)。

#include <iostream>
using namespace std;
const int N = 1e5 + 10, MOD = 1e5 + 3;
int n, k;
int dp[N], sum[N];
int main() {
    cin >> n >> k;
    dp[0] = 1;
    sum[0] = dp[0];
    for (int i = 1; i <= n; i++) {
        if (i - k > 0) {
            dp[i] = (sum[i-1] - sum[i - k - 1] + MOD) % MOD;
        } else {
            dp[i] = sum[i-1] % MOD;
        }
        sum[i] = (sum[i-1] + dp[i]) % MOD;
    }
    cout << dp[n] << endl;
    return 0;
}

例题 2：最大子段和（洛谷 P1115）—— 一维线性 DP 的最值问题

题目描述

给出一个长度为 n 的序列 a，选出其中连续且非空的一段，使得这段的和最大。 输入：第一行是序列长度 n；第二行是 n 个整数（-1e4 ≤ a[i] ≤ 1e4，1≤n≤2e5） 输出：最大子段和

思路拆解

1. 状态表示：dp[i] 表示'以第 i 个元素为结尾的所有连续子段的最大和'。
2. 状态转移方程：dp[i] = max(a[i], dp[i-1] + a[i])
3. 初始化：dp[1] = a[1]。
4. 填表顺序：从左到右依次计算，最终答案是 dp 数组中的最大值。

代码实现

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 2e5 + 10;
int n;
int a[N], dp[N];
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    dp[1] = a[1];
    int max_sum = dp[1];
    for (int i = 2; i <= n; i++) {
        dp[i] = max(a[i], dp[i-1] + a[i]);
        max_sum = max(max_sum, dp[i]);
    }
    cout << max_sum << endl;
    return 0;
}

空间优化：O(1) 空间

观察发现，dp[i] 只依赖 dp[i-1]，因此不需要用数组存储整个 dp 序列，只用一个变量记录前一个状态即可。

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 2e5 + 10;
int n;
int a[N];
int main() {
    cin >> n;
    int prev = 0, max_sum = -1e9;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        prev = max(a[i], prev + a[i]);
        max_sum = max(max_sum, prev);
    }
    cout << max_sum << endl;
    return 0;
}

例题 3：传球游戏（洛谷 P1057）—— 二维线性 DP 的状态设计

题目描述

n 个同学站成一个圆圈，小蛮（1 号同学）手里拿着球，传了 m 次后，球回到小蛮手里的不同传球方法有多少种？ 输入：两个整数 n, m（3≤n≤30，1≤m≤30） 输出：符合条件的传球方法数

思路拆解

1. 状态表示：dp[i][j] 表示'传球 i 次后，球在第 j 号同学手里的方法数'。
2. 状态转移方程：
   • 中间同学：dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]
   • 1 号同学：dp[i][1] = dp[i-1][n] + dp[i-1][2]
   • n 号同学：dp[i][n] = dp[i-1][n-1] + dp[i-1][1]
3. 初始化：dp[0][1] = 1。
4. 填表顺序：先枚举传球次数 i，再枚举同学编号 j。

代码实现

#include <iostream>
using namespace std;
const int N = 50;
int n, m;
int dp[N][N];
int main() {
    cin >> n >> m;
    dp[0][1] = 1;
    for (int i = 1; i <= m; i++) {
        dp[i][1] = dp[i-1][n] + dp[i-1][2];
        for (int j = 2; j < n; j++) {
            dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1];
        }
        dp[i][n] = dp[i-1][n-1] + dp[i-1][1];
    }
    cout << dp[m][1] << endl;
    return 0;
}

例题 4：乌龟棋（洛谷 P1541）—— 多维线性 DP 的状态优化

题目描述

乌龟棋的棋盘有 N 个格子，每个格子有分数。玩家有 M 张爬行卡片，分为 4 种类型（1、2、3、4），每张卡片只能用一次。乌龟从第 1 格出发，用完全部卡片到达第 N 格，求最大得分。 输入：

• 第一行：N, M（1≤N≤350，1≤M≤120）
• 第二行：N 个整数，第 i 个是第 i 格的分数
• 第三行：M 个整数，每张卡片的类型 输出：最大得分

思路拆解

1. 状态表示：dp[a][b][c][d] 表示'使用 a 张 1 型、b 张 2 型、c 张 3 型、d 张 4 型卡片时的最大得分'，对应位置 pos = 1 + a + 2b + 3c + 4d。
2. 状态转移方程：dp[a][b][c][d] = max(四种前序状态) + score[pos]
3. 初始化：dp[0][0][0][0] = score[1]。
4. 填表顺序：从小到大枚举四种卡片的使用次数。

代码实现

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 360, M = 50;
int n, m;
int score[N];
int cnt[5];
int dp[M][M][M][M];
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> score[i];
    }
    for (int i = 0; i < m; i++) {
        int t;
        cin >> t;
        cnt[t]++;
    }
    dp[0][0][0][0] = score[1];
    for (int a = 0; a <= cnt[1]; a++) {
        for (int b = 0; b <= cnt[2]; b++) {
            for (int c = 0; c <= cnt[3]; c++) {
                for (int d = 0; d <= cnt[4]; d++) {
                    int pos = 1 + a + 2*b + 3*c + 4*d;
                    int& curr = dp[a][b][c][d];
                    if (a > 0) curr = max(curr, dp[a-1][b][c][d] + score[pos]);
                    if (b > 0) curr = max(curr, dp[a][b-1][c][d] + score[pos]);
                    if (c > 0) curr = max(curr, dp[a][b][c-1][d] + score[pos]);
                    if (d > 0) curr = max(curr, dp[a][b][c][d-1] + score[pos]);
                }
            }
        }
    }
    cout << dp[cnt[1]][cnt[2]][cnt[3]][cnt[4]] << endl;
    return 0;
}

复杂度分析

四种卡片的最大数量都是 40，四维循环总次数是 40^4 = 2,560,000，完全可以通过。

三、线性 DP 常见优化技巧总结

1. 空间优化：滚动数组 / 变量。如果当前状态只依赖前几个状态，只用存储必要的前序状态。
2. 时间优化：前缀和 / 后缀和。当状态转移需要求和，用前缀和数组预处理，将 O(K) 转化为 O(1)。
3. 状态维度优化：通过数学关系减少 DP 数组的维度。
4. 边界处理优化：合理设置边界值，避免越界或逻辑错误。

四、线性 DP 实战练习建议

1. 基础巩固：洛谷 P10250 下楼梯、P1115 最大子段和、P1057 传球游戏。
2. 进阶练习：洛谷 P1541 乌龟棋、P1216 数字三角形。
3. 总结归纳：思考状态定义、转移方程推导及优化空间。

总结

线性 DP 是后续学习背包 DP、区间 DP 等复杂 DP 的基础。打好这个基础，后面的学习会事半功倍。祝大家都能攻克 DP 这个难点，在算法路上越走越远！