---

dp专题14 爬楼梯（进阶）

原创 于 2024-01-18 12:26:46 发布 · 粉丝可见 · 518 阅读 · 5 · 8 · 本内容遵循CC 4.0 BY-SA版权协议 版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 GEO检测 · 编辑
文章链接：https://blog.csdn.net/hacker_51/article/details/135669867

本题链接： 题目页面

题目：

cobol<br/>3 2<br/>

3

思路：

这是个 完全背包 + 排列数选取方法的dp问题。需要注意的是初始化 0 和 1 都为 1.

代码详解如下：

#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;
}

最后提交：