本题链接：题目页面
题目：
|
| 3 |
文章来源：https://www.toymoban.com/news/detail-801401.html
思路：
这是个 完全背包 + 排列数选取方法的dp问题。需要注意的是初始化 0 和 1 都为 1.文章来源地址https://www.toymoban.com/news/detail-801401.html
代码详解如下：
#include <iostream>
#include <vector>
#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false),cin.tie(0)
using namespace std;
inline void solve()
{
int n,m;
cin >> n >> m;
vector<int>dp(n + 1,0); // 定义 dp 数组
// 初始化 dp ， 第 0 个台阶 和 第 1 个台阶 有 1 中方法
dp[0] = 1;
dp[1] = 1;
// 假设 上 3 个台阶 ， 先 1 后 2 和 先 2 后 1 是两种不同的方法
// 所以这是个排列数， 所以我们应该先遍历 背包，再遍历物品
for(int i = 2;i <= n;++i) // 这里 i 先从 2 开始 是因为我们前面初始化 过 0 和 1 了
{
for(int j = 1;j <= m;++j) // 这里 j 从 1 开始 是没必要 选择 0 阶台阶的选法
{
if(i >= j) dp[i] += dp[i - j];
}
}
cout << dp[n] << endl;
}
signed main()
{
IOS;
int t = 1;
// cin >> t;
while(t--)
{
solve();
}
return 0;
}
最后提交：
到了这里，关于dp专题14 爬楼梯（进阶）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
