线性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];}
};
更多推荐
[线性dp][完全背包]leetcode70:爬楼梯(eary)
发布评论