思路：把"两个整数组成的复合状态"直接当键。pair 自带 operator<，所以 map 能直接用它。
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
map<pair<int, int>, long long> memo;
// 状态：还剩 rem 级台阶要走，本步最多跨 k 级
long long dfs(int rem, int k) {
if (rem == 0) return 1; // 走到顶，算一种方案
if (rem < 0) return 0;
auto key = make_pair(rem, k);
// ★★ 必须用 find 判断存在性 ★★
auto it = memo.find(key);
if (it != memo.end()) return it->second;
long long res = 0;
for (int step = 1; step <= k && step <= rem; step++) {
res = (res + dfs(rem - step, k)) % MOD;
}
memo[key] = res; // 只在确定要写入时才用 []
return res;
}
int main() {
int n, k;
scanf("%d %d", &n, &k);
printf("%lld\n", dfs(n, k));
printf("状态数 = %zu\n", memo.size()); // 顺便观察记忆化效果
return 0;
}
输入输出示例（n=5, k=2：每步 1 或 2 级，共有 8 种走法）：
🔍 参考代码逐段解析（以 n=5, k=2 手算）
① 边界两连：rem == 0 返回 1（一步不剩 = 恰好走完，算 1 种方案）；rem < 0 返回 0（跨过头了，非法方案）—— 两个边界缺一不可，少了后者递归会跑飞。
② auto key = make_pair(rem, k);：把二维状态打包成 pair；pair 自带 operator<，所以 map<pair<int,int>, long long> 不需要任何额外代码。
③ memo.find(key)（本题灵魂）：find 只查不插；找不到才往下算。若写成 memo[key]，一次读就会把状态以 0 塞进表 —— "没算过"和"算出 0"再也无法区分。
④ 转移循环：for (step = 1; step <= k && step <= rem; ...) — 上界取 min(k, rem)，保证 rem−step ≥ 0；每项累加后立即 % MOD，防止 long long 溢出。
⑤ memo[key] = res;：只在确定要写入时用 operator[] —— "读用 find、写用 []" 是 map 的标准分工。
手算验证：f(0)=1；f(1)=f(0)=1；f(2)=f(1)+f(0)=2；f(3)=f(2)+f(1)=3；f(4)=5；f(5)=f(4)+f(3)=5+3=8，与示例输出一致；计算过的状态是 (rem,k) 中 rem=1..5，共 5 个，"状态数 = 5" 也对上了。
易错点：① 用 memo[key] 判存在性（本题最致命错误）；② 忘 % MOD；③ 忘 rem<0 边界；④ main 里忘记 memo 是全局的 —— 若把它放进 main 或函数内，每次调用都是空表，记忆化完全失效（还可能栈溢出）。
② 为什么必须用 find 而不能用 memo[key]？
因为 map::operator[] 有"自动插入"的副作用：如果键不存在，它会插入一个"值初始化为 0"的元素并返回引用。在这个算法里有两重危害：
危害一 · 逻辑彻底错误（最致命）。你写 if (memo[key] != 0) return memo[key]; 想判"算过没有"，但 memo[key] 这一读就已经把状态插进去了，值为 0。而"算出来真的等于 0"的状态（本例中 k=0 或 rem 无法走到的情况）也表现为 0。两者完全无法区分 —— 于是"没算过"被误判成"算过且答案是 0"，直接返回错误结果。
危害二 · 内存与状态数失控。每个查询（包括那些最终没被使用的）都会在表里留下条目。本来 O(n) 个状态可能膨胀成远超预期的数量，导致 MLE。
正确的判存在性三种写法：
// 写法 1：find（推荐，只查一次）
auto it = memo.find(key);
if (it != memo.end()) return it->second;
// 写法 2：count
if (memo.count(key)) return memo[key];
// 写法 3：C++20 的 contains（更直观）
// if (memo.contains(key)) return memo[key];
小对比：count + operator[] 会查询两次（多一次 O(log n)）；find 只查一次，所以是首选。如果确实想用 operator[]，就必须用不会冲突的初值做哨兵（比如把"未访问"标记为 -1，因为方案数不会为负）——但这样又依赖"值域不与哨兵冲突"这个隐含假设，容易出问题，不如用 find 明确。
③ 改用 unordered_map 需要做的额外工作：
关键问题：unordered_map 需要"把键映射成哈希值"，而标准库只为内置类型和 string 提供了哈希函数，pair 没有。所以直接写 unordered_map<pair<int,int>, long long> 会编译错误（提示 no matching function for call to hash<pair<int,int>>）。
解决方案一（推荐）：把 pair 编码成一个整数。
// 用 long long 组合两个 int（保证不冲突、不溢出）
unordered_map<long long, long long> memo;
auto encode = [](int a, int b) -> long long {
return (long long)a * 2000000000LL + b; // b 的取值范围必须小于这个倍数
};
auto it = memo.find(encode(rem, k));
if (it != memo.end()) return it->second;
// ... memo[encode(rem, k)] = res;
编码要点：① 倍数必须严格大于 b 的最大可能取值，否则不同 (a,b) 会编码成同一个数（哈希冲突变成语义冲突，必错无疑）；② 乘法要用 long long，a × 倍数 不能溢出；③ 建议在注释里写清 a、b 各自的取值范围，方便日后检查。
解决方案二：自定义哈希函数。写一个 struct PairHash { size_t operator()(const pair<int,int>& p) const {...} }，作为第三个模板参数传给 unordered_map。代码更长，而且要自己保证哈希质量（否则大量冲突会让平均 O(1) 退化成 O(n)）。
什么时候值得换 unordered_map？当状态数很大（比如 106 以上）且常数敏感时。unordered_map 的平均查询是 O(1)，比 map 的 O(log n) 常数小得多。但必须注意：它可能被构造数据卡到最坏 O(n)，竞赛中若出题人刻意卡哈希就要加随机化种子。
最后一个更优的选择：如果 n 和 k 的范围允许（比如 n × k ≤ 107），直接开二维 vector 数组 + 一个访问标记数组，比任何哈希/树结构都快。这再次印证了知识点 1 的结论：能用连续内存的数组，就不要用树或哈希表。
易错：① 用 memo[key] 判存在性（最常见也最致命）；② 编码时倍数取小了，两个不同状态编码成同一个数；③ 编码时用 int 乘法溢出；④ 忘记取模导致答案溢出；⑤ 忘记处理 rem < 0 的边界（step > rem 时递归会得到负数）。