线性动态规划核心解析
线性 DP 是动态规划中最基础、最常见的一类问题。其特点是状态转移只依赖于前一个或前几个状态,关系呈线性,通常可用一维或二维数组存储。我们在入门阶段解决的《下楼梯》以及《数字三角形》其实都属于此类,前者是一维,后者是二维。
台阶问题
题目描述

解题思路
本题可视为下楼梯问题的加强版,总体思路不变。我们按照标准动规分析步骤来拆解:
- 状态表示:
dp[i]表示走到第i个台阶的所有方案数。 - 状态转移方程:第
i个台阶的方案数等于从i-1阶到i-k阶所有方案数之和。由于数据较大,结果需对100003取模。注意边界检查,避免访问负下标。dp[i] = (dp[i] + dp[i - j]) % MOD; // j 从 1 到 k - 初始化:将
dp[0]置为 1 即可完成初始化,然后从dp[1]开始循环计算。 - 填表顺序:从左往右。
- 输出结果:
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++) {
( j = ; j <= k; j++) {
(i - j < ) ;
dp[i] = (dp[i] + dp[i - j]) % MOD;
}
}
cout << dp[n] << endl;
;
}





