线性动态规划是动态规划问题中最基础、最常见的一类。它的特点是状态转移只依赖于前一个或前几个状态,状态之间的关系是线性的,通常可以用一维或者二维数组来存储状态。我们在入门阶段解决的《下楼梯》以及《数字三角形》其实都是线性 DP,一个是一维的,另一个是二维的。下面我们通过四个经典题目来深入理解这一类问题的解法。
台阶问题
本题可以看作是《下楼梯》问题的加强版,总体思路不变。按照动态规划的常规步骤来分析这道题。
状态表示
dp[i] 表示走到第 i 个台阶的所有方案数。
状态转移方程
第 i 个台阶的方案数等于从 i-1 阶到 i-k 阶的所有方案数之和。由于数据较大,结果需要对 100003 取模。需要注意的是,访问台阶时需要保证 i-j 始终大于等于 0,防止负下标越界。
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++) {
for (int j = 1; j <= k; j++) {
// 保证不越界访问
if (i - j < 0) break;
dp[i] = (dp[i] + dp[i - j]) % MOD;
}
}
cout << dp[n] << endl;
;
}


