线性 DP 经典四题详解

线性 DP 简介

线性动态规划（Linear DP）是动态规划问题中最基础、最常见的一类问题。它的特点是状态转移只依赖于前一个或前几个状态，状态之间的关系是线性的，通常可以用一维或者二维数组来存储状态。

台阶问题

题目描述

有 n 个台阶，每次可以走 1 到 k 步，求走到第 n 个台阶的方案数。结果对 100003 取模。

题目解析

1. 状态表示 dp[i] 表示走到第 i 个台阶的所有方案数。
2. 状态转移方程 第 i 个台阶的方案数等于从 i-1 阶到 i-k 阶的所有方案数之和。注意数据可能越界，访问台阶时需要保证 i-j 始终大于等于 0。 dp[i] = (dp[i] + dp[i - j]) % 100003 （j 从 1 到 k）。
3. 初始化 将 dp[0] 置为 1 即可完成初始化操作，然后从 dp[1] 开始往后循环计算方案数。
4. 填表顺序 从左往右。
5. 输出结果 dp[n] 即为结果。

代码实现

#include <iostream>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10, MOD = 1e5 + 3;
int n, k;
LL dp[N];

int main(){
    cin >> n >> k;
    // 初始化
    dp[0] = 1;
    // 循环填表
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= k; j++){
            // 保证不越界访问
            if(i - j < 0) break;
            dp[i] = (dp[i] + dp[i - j]) % MOD;
        }
    }
    // 输出结果
    cout << dp[n] << endl;
     ;
}