线性DP

线性DP是所有动态规划问题的基础，它的核心思想非常简单：把问题拆成按顺序排列的小问题，先解决前面的小问题，再用前面的答案推导后面的答案。

所有线性DP问题都遵循同一个解题框架：

1. 定义dp[i]：表示处理到第i个位置时的最优解
2. 找出转移关系：dp[i]可以从哪些dp[j]（j < i）转移过来
3. 确定初始值：dp[0]或dp[1]的已知值
4. 按顺序从1到n计算所有dp[i]

一、最长上升子序列（LIS）

问题重述

给你一个长度为n的数字序列，比如[3, 1, 4, 1, 5, 9]。你需要从中选出一些数字，保持它们在原序列中的相对顺序，并且这些数字是严格递增的。问这样的子序列最长有多长？

比如上面的例子，最长上升子序列是[1, 4, 5, 9]，长度是4。

第一步：定义状态

这是DP最关键的一步。我们定义：

dp[i] = 以第i个数字结尾的最长上升子序列的长度

为什么要定义成"以第i个数字结尾"？
因为如果我们想在后面接一个更大的数字，只需要知道最后一个数字是多少就行了。比如dp[5] = 3表示以第5个数字结尾的最长子序列长度是3，那么只要第6个数字比第5个大，我们就可以把它接在后面，得到长度为4的子序列。

这里容易理解成dp[i] = 到第i个数字为止的最长上升子序列的长度，这是错误的

第二步：推导状态转移

对于第i个数字，我们有两种选择：

1. 它自己单独成为一个子序列，长度是1
2. 把它接在前面某个比它小的数字后面，长度就是那个数字的dp[j] + 1

所以对于每个i，我们需要遍历它前面所有的j（1 ≤ j < i）：

• 如果a[j] < a[i]，说明可以接在j后面，那么dp[i] = max(dp[i], dp[j] + 1)
• 如果a[j] >= a[i]，说明不能接，跳过

第三步：确定初始值

每个数字自己都能构成一个长度为1的子序列，所以所有dp[i]的初始值都是1。

第四步：用样例填表理解

我们用序列[3, 1, 4, 1, 5]来填个表：

最终答案就是所有dp[i]中的最大值，也就是3。

完整代码

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

const int N = 1005;
int a[N]; // 存原序列
int dp[N]; // dp[i]表示以第i个元素结尾的最长上升子序列长度

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    
    int ans = 0;
    // 外层循环：按顺序处理每个元素
    for (int i = 1; i <= n; i++) {
        dp[i] = 1; // 初始值：自己单独一个子序列
        // 内层循环：遍历前面所有元素
        for (int j = 1; j < i; j++) {
            // 如果前面的元素比当前小，就可以接在后面
            if (a[j] < a[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        // 更新全局最大值
        ans = max(ans, dp[i]);
    }
    
    cout << ans << endl;
    return 0;
}

二、P1359 租用游艇

这道题是线性DP的直接应用，和LIS的代码结构几乎一模一样。

问题重述

有n个游艇出租站，从上游到下游编号1到n。你可以在任意一个站租游艇，然后在下游任意一个站还。从站i到站j的租金是r[i][j]。问从站1到站n最少需要花多少钱？

比如样例输入：

3
5 15
7

意思是：

• 1→2租金5，1→3租金15
• 2→3租金7

最优方案是1→2→3，总租金5+7=12。

第一步：定义状态

非常直观：

dp[i] = 从站1到站i的最少租金

第二步：推导状态转移

要到达站i，你只能从它上游的某个站j直接过来（因为不能往回走）。所以：

• 对于所有j < i，你都可以先花dp[j]的钱到达j，然后再花r[j][i]的钱从j直接到i
• dp[i]就是所有这些可能中的最小值

状态转移方程：
dp[i] = min(dp[i], dp[j] + r[j][i]) （对所有1 ≤ j < i）

第三步：确定初始值

• dp[1] = 0：从站1到站1不需要花钱
• 其他所有dp[i]初始化为一个很大的数（比如1e9），表示一开始还不知道怎么到达

第四步：输入处理（重点）

这道题的输入是一个上三角半矩阵，很多同学会在这里卡壳：

• 第1行有n-1个数：分别是r[1][2], r[1][3], ..., r[1][n]
• 第2行有n-2个数：分别是r[2][3], r[2][4], ..., r[2][n]
• ...
• 第n-1行有1个数：r[n-1][n]

所以我们可以这样读入：

for (int i = 1; i <= n-1; i++) { // 出发站
    for (int j = i+1; j <= n; j++) { // i出发的所有可能到达站
        cin >> r[i][j];
    }
}

第五步：样例计算过程

样例n=3：

1. dp[1] = 0
2. 计算dp[2]：只能从1过来，dp[2] = dp[1] + r[1][2] = 0 + 5 = 5

3. 计算dp[3]：

   • 从1过来：dp[1] + r[1][3] = 0 + 15 = 15
   • 从2过来：dp[2] + r[2][3] = 5 + 7 = 12
   • 取最小值，dp[3] = 12

最终答案就是dp[3] = 12，和样例一致。

完整代码

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

const int N = 205;
const int INF = 1e9;
int r[N][N]; // r[i][j]表示从i到j的租金
int dp[N]; // dp[i]表示从1到i的最少租金

int main() {
    int n;
    cin >> n;
    
    // 读入半矩阵
    for (int i = 1; i <= n-1; i++) {
        for (int j = i+1; j <= n; j++) {
            cin >> r[i][j];
        }
    }
    
    // 初始化dp数组
    for (int i = 1; i <= n; i++) {
        dp[i] = INF;
    }
    dp[1] = 0; // 初始值
    
    // 外层循环：按顺序处理每个站
    for (int i = 2; i <= n; i++) {
        // 内层循环：遍历前面所有站
        for (int j = 1; j < i; j++) {
            // 从j到i，更新最小值
            dp[i] = min(dp[i], dp[j] + r[j][i]);
        }
    }
    
    cout << dp[n] << endl;
    return 0;
}

你看，这个代码结构和LIS几乎完全一样：外层循环i从1到n，内层循环j从1到i-1，用j的状态更新i的状态。

三、P2800 又上锁妖塔

这道题稍微复杂一点，需要用两个DP数组，但本质还是线性DP。

问题重述

锁妖塔有n层，每层高度h[i]。你可以：

1. 爬一层：花费h[i]的时间，爬完之后可以继续爬或者跳
2. 跳一层或两层：不花费时间，但跳完之后必须至少爬一层才能再跳

问从地面爬到第n层的最少时间是多少？

比如样例输入：

5
3 5 1 8 4

最优方案是：从地面跳2层到第2层（不花时间），然后爬第3层（花1时间），然后跳2层到第5层（不花时间）。总时间1。

第一步：为什么需要二维状态？

因为你当前能做什么动作，取决于你上一步做了什么动作：

• 如果上一步是爬，那么下一步可以爬，也可以跳
• 如果上一步是跳，那么下一步只能爬，不能跳

所以我们需要用两个状态来区分最后一步的动作：

climb[i] = 到达第i层，且最后一步是爬的最少时间
jump[i] = 到达第i层，且最后一步是跳的最少时间

第二步：推导状态转移

我们分别推导这两个状态的转移方程：

1. 最后一步是爬（climb[i]）

最后一步是爬，说明你是从第i-1层爬上来的。
而你在第i-1层的时候，最后一步不管是爬还是跳都可以，因为爬完之后没有限制。
所以：
climb[i] = min(climb[i - 1], jump[i - 1]) + h[i]

2. 最后一步是跳（jump[i]）

最后一步是跳，说明你是从前面某一层跳上来的，而且跳之前的最后一步必须是爬（因为跳完之后必须爬才能再跳）。
你可以跳1层（从i-1跳上来），也可以跳2层（从i-2跳上来）。
所以：
jump[i] = min(climb[i - 1], climb[i - 2])

第三步：确定初始值

我们需要处理边界情况：

• climb[1] = h[1]：爬第1层，花费h[1]时间
• jump[1] = INF：不可能从地面跳1层到第1层（因为跳之前必须爬过至少一层）
• climb[2] = climb[1] + h[2]：从第1层爬上来
• jump[2] = climb[1]：从第1层跳1层上来（跳之前是爬）

第四步：样例计算过程

样例n=5，h=[3,5,1,8,4]：

• 地面可以看作第0层，climb[0] = 0（在地面，相当于最后一步是爬）
• climb[0] = 0
• climb[1] = climb[0] + 3 = 3，jump[1] = INF
• climb[2] = min(3, INF) + 5 = 8，jump[2] = min(climb[1], climb[0]) = 0
• climb[3] = min(8, 0) + 1 = 0 + 1 = 1
jump[3] = min(climb[2], climb[1]) = min(8, 3) = 3
• climb[4] = min(1, 3) + 8 = 1 + 8 = 9
jump[4] = min(climb[3], climb[2]) = min(1, 8) = 1
• climb[5] = min(9, 1) + 4 = 1 + 4 = 5
jump[5] = min(climb[4], climb[3]) = min(9, 1) = 1

最终答案min(5, 1) = 1，

完整代码

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

const int N = 1e6 + 7;
const int INF = 1e9;
int h[N];
int climb[N]; // 到达第i层，最后一步是爬的最短时间
int jump[N];  // 到达第i层，最后一步是跳的最短时间

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> h[i];
    }
    
    // 初始化
    climb[0] = 0; // 地面，相当于最后一步是爬
    jump[0] = INF;
    climb[1] = h[1];
    jump[1] = INF;
    
    // 按顺序处理每一层
    for (int i = 2; i <= n; i++) {
        // 最后一步是爬：从i-1任意状态爬上来
        climb[i] = min(climb[i-1], jump[i-1]) + h[i];
        // 最后一步是跳：从i-1或i-2的爬状态跳上来
        jump[i] = min(climb[i-1], climb[i-2]);
    }
    
    cout << min(climb[n], jump[n]) << endl;
    return 0;
}

四、线性DP共通性总结

这三道题看起来完全不同，但它们的核心逻辑是一模一样的：

1. 状态按顺序排列：所有状态都是按1,2,3,...,n的顺序排列的，我们必须严格按这个顺序计算
2. 转移单向性：第i个状态只能从它前面的状态（j < i）转移过来，永远不会用到后面的状态

3. 代码结构高度统一：

   // 初始化dp数组
   dp[0] = 初始值;
   
   // 外层循环：按顺序处理每个位置
   for (int i = 1; i <= n; i++) {
       // 内层循环：遍历所有可能转移过来的前面的位置
       for (int j = 1; j < i; j++) {
           dp[i] = 最优值(dp[i], dp[j] + 转移代价);
       }
   }
   
   cout << dp[n] << endl;