[线性dp][完全背包]leetcode70：爬楼梯(eary)

线性dp][完全背包]leetcode70：爬楼梯(eary)"/>

[线性dp][完全背包]leetcode70：爬楼梯(eary)

题目：

题解：

使用动态规划思路：线性 dp 递推 and 完全背包求排列数思路。

代码如下：

// 2022/5/14 动态规划两种解法
const int N = 50;
int f[N];// f[i]表示爬到第i阶台阶的方案数量
class Solution {
public:int climbStairs(int n) {return dp1(n);}// 完全背包：恰好装满n的物品的所有方案数（每个物品可被使用无限次）int dp1(int n){// 初始化为0，可以将装不满的状态设为无效值0memset(f,0,sizeof f);// 装满体积0和体积1的方案数各为1f[0]=1;// 这里先遍历背包，再遍历物品，用来统计所有的排列数for(int j=0;j<=n;++j)for(int i=1;i<=2;++i)if(j>=i)f[j]+=f[j-i];return f[n];}// 线性dp的思路int dp2(int n){memset(f,0,sizeof f);// 初始状态：爬到0阶和1阶的方案数都是1步f[0]=f[1]=1;// 状态转移：第i阶台阶由第i-1阶台阶和第i-2阶台阶转移而来for(int i=2;i<=n;++i)f[i]=f[i-1]+f[i-2];return f[n];}
};