蔚县网站建设公司,我要注册,idzoom室内设计师网,威海网站制作怎么样文章目录 1. 每日一言2. 题目2.1 解题思路2.1.1 递归2.1.2 记忆化搜索2.1.3 动态规划2.1.4 动态规划空间优化 2.2 代码2.2.1 递归2.2.2 记忆化搜索2.2.3 动态规划2.2.4 动态规划空间优化 3. 结语 1. 每日一言
Happy life lies in a peaceful mind. 幸福的生活存在于心绪的宁静… 文章目录 1. 每日一言2. 题目2.1 解题思路2.1.1 递归2.1.2 记忆化搜索2.1.3 动态规划2.1.4 动态规划空间优化 2.2 代码2.2.1 递归2.2.2 记忆化搜索2.2.3 动态规划2.2.4 动态规划空间优化 3. 结语 1. 每日一言
Happy life lies in a peaceful mind. 幸福的生活存在于心绪的宁静之中。 2. 题目
题目链接爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢 示例 1 输入n 2 输出2 解释有两种方法可以爬到楼顶。 1. 1 阶 1 阶 2. 2 阶 示例 2 输入n 3 输出3 解释有三种方法可以爬到楼顶。 1. 1 阶 1 阶 1 阶 2. 1 阶 2 阶 3. 2 阶 1 阶
提示
1 n 45 2.1 解题思路
2.1.1 递归 首先函数判断如果 n 小于等于 2则直接返回 n。因为在楼梯阶数小于等于 2 的情况下只有一种方式爬到顶部即分别走一步或者直接跨两步。 对于大于 2 的情况函数采用递归的方式进行计算。爬到第 n 阶楼梯的方式数量等于爬到第 n-1 阶和第 n-2 阶的方式数量之和。这是因为爬到第 n 阶楼梯只有两种方式一种是从第 n-1 阶再爬一阶另一种是从第 n-2 阶再跨两阶。 最后将计算得到的方式数量 sum 返回。
2.1.2 记忆化搜索
首先定义一个全局数组 men大小为 46因为题目中规定楼梯数不超过 45。这个数组用来保存已经计算过的楼梯阶数对应的爬楼梯方式数量避免重复计算。接下来定义一个递归函数 climb(int n)用来计算爬到第 n 阶楼梯的方式数量。如果 n 小于等于 2则直接返回 n表示只有一种或两种方式爬到顶部。如果 men[n] 不为 -1说明之前已经计算过爬到第 n 阶楼梯的方式数量直接返回 men[n]。如果 men[n] 为 -1说明还没有计算过爬到第 n 阶楼梯的方式数量此时调用递归函数 climb(n-1) climb(n-2) 来计算并将结果保存在 men[n] 中然后返回该结果。最后在 climbStairs 函数中将 men 数组初始化为 -1并调用 climb 函数来求解爬楼梯问题。
2.1.3 动态规划
首先定义一个长度为 46 的整型数组 climb用来存储爬到每个楼梯阶数的方式数量。数组初始化为 [1, 2]表示爬到第一阶和第二阶楼梯的方式数量分别为 1 和 2。接下来使用一个循环从第三阶楼梯开始计算爬楼梯的方式数量。对于第 i 阶楼梯爬到这一阶的方式数量等于爬到第 i-1 阶和第 i-2 阶的方式数量之和因为只有两种方式可以到达第 i 阶楼梯要么是从第 i-1 阶跨一步要么是从第 i-2 阶跨两步。最后返回数组 climb 中第 n-1 个元素即爬到第 n 阶楼梯的方式数量。
2.1.4 动态规划空间优化
如果输入的楼梯阶数 n 小于等于 2那么直接返回 n因为在这种情况下只有一阶或者两阶楼梯爬到顶部的方式数量分别为 1 和 2。对于大于 2 的情况定义三个变量 a、b 和 c分别表示爬到第 n-2、第 n-1 和第 n 阶楼梯的方式数量。初始时a 被赋值为 1表示爬到第一阶楼梯的方式数量b 被赋值为 2表示爬到第二阶楼梯的方式数量。使用一个循环来计算爬到第 n 阶楼梯的方式数量。循环从第 3 阶楼梯开始依次计算爬到每一阶楼梯的方式数量直到计算到第 n 阶为止。在循环中更新 c 的值为 a b然后将 b 的值赋给 a将 c 的值赋给 b以便继续下一轮循环。循环结束后c 中存储的就是爬到第 n 阶楼梯的方式数量。最后返回 c。
2.2 代码
2.2.1 递归
int climbStairs(int n) {if(2 n) {return n;}int sum 0;sum climbStairs(n-1) climbStairs(n-2);return sum;
}2.2.2 记忆化搜索
int men[46];
int climb(int n) {if(n 2) {return n;}if(men[n] ! -1) {return men[n];}return men[n] climb(n-1) climb(n-2);;
}
int climbStairs(int n) {for(int i 0; i 46; i) {men[i] -1;}return climb(n);
}2.2.3 动态规划
int climbStairs(int n) {int climb[46];climb[0] 1;climb[1] 2;for(int i 2; i n; i) {climb[i] climb[i-1] climb[i-2];}return climb[n-1];
}2.2.4 动态规划空间优化
int climbStairs(int n) {if(n 2) {return n;} else {int a 1;int b 2;int c 0;while(n 2) {c a b;a b;b c;--n;}return c;}
}3. 结语
请给自己些耐心不要急于求成。 山外青山楼外楼莫把百尺当尽头。 保持空杯心态加油努力吧 都看到这里啦真棒(*^▽^*)
可以给作者一个免费的赞赞吗这将会鼓励我继续创作谢谢大家
编程小白写作如有纰漏或错误欢迎指正
