建设网站需要服务器吗,有多少人自己做电影网站,无锡网络推广方案服务,千库网下载爬楼梯
题目描述
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢#xff1f;
示例 1#xff1a;
输入#xff1a;n 2 输出#xff1a;2 解释#xff1a;有两种方法可以爬到楼顶。
1 阶 1 阶2 阶
示…爬楼梯
题目描述
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢
示例 1
输入n 2 输出2 解释有两种方法可以爬到楼顶。
1 阶 1 阶2 阶
示例 2
输入n 3 输出3 解释有三种方法可以爬到楼顶。
1 阶 1 阶 1 阶1 阶 2 阶2 阶 1 阶
提示
1 n 45
动规五部曲
定义⼀个⼀维数组来记录不同楼层的状态
确定dp数组以及下标的含义 dp[i] 爬到第i层楼梯有dp[i]种⽅法确定递推公式 从第三层开始第n层需要的步伐等于第n-1层需要的步伐加上第n-2层需要的步伐 例如第三层第一层2 第二层1 第四层第二层2 第三层1dp数组如何初始化 不考虑dp[0]如何初始化只初始化dp[1] 1dp[2] 2然后从i 3开始递推这样才符合 dp[i]的定义。确定遍历顺序 从递推公式dp[i] dp[i - 1] dp[i - 2];中可以看出遍历顺序⼀定是从前向后遍历的举例推导dp数组 举例当n为5的时候dp tabledp数组应该是这样的 如果代码出问题了就把dp table 打印出来看看究竟是不是和⾃⼰推导的⼀样。 此时⼤家应该发现了这不就是斐波那契数列么 唯⼀的区别是没有讨论dp[0]应该是什么因为dp[0]在本题没有意义
代码
力扣提交代码
class Solution {
public:int climbStairs(int n) {if (n 1) return n; // 因为下⾯直接对dp[2]操作了防⽌空指针vectorint dp(n 1);dp[1] 1;dp[2] 2;for (int i 3; i n; i) { // 注意i是从3开始的dp[i] dp[i - 1] dp[i - 2];}return dp[n];}
};总代码
#includebits/stdc.h
using namespace std;int climbStairs(int n)
{if(n2)return n;int dp[50]{0};dp[1]1;dp[2]2;int i;for(i3;in;i)dp[i]dp[i-1]dp[i-2];return dp[n];
}int main()
{int n;scanf(n %d,n);coutclimbStairs(n);return 0;
}
