济南网站制作经验,微信网站链接网站建设,企业邮箱网易登录入口,两题一做的网站一、题目描述
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢#xff1f;
二、测试用例
示例 1#xff1a;
输入#xff1a;n 2
输出#xff1a;2
解释#xff1a;有两种方法可以爬到楼顶。
1. 1 阶…一、题目描述
假设你正在爬楼梯。需要 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 阶二、解题思路
基本思路记爬 2 个台阶的个数为 k 该题目可以转化为计算 k 012…的方案数例如k 0表示每次只爬一个台阶方案数为 C n − k k C n 0 1 C_{n-k}^kC_n^01 Cn−kkCn01 k 1 表示有一次是爬两个台阶其他都是爬一个台阶方案数就是 C n − k k C n − 1 1 n − 1 C_{n-k}^kC_{n-1}^1n-1 Cn−kkCn−11n−1 依次类推总方案数就是 ∑ k 0 n 2 C n − k k \sum_{k0}^{\frac n2}C_{n-k}^k k0∑2nCn−kk具体思路 暴力解写一个函数计算 C n k n ( n − 1 ) ⋯ ( n − k 1 ) k ! C_n^k\frac{n(n-1)\cdots(n-k1)}{k!} Cnkk!n(n−1)⋯(n−k1)动态规划计算 C n k C_n^k Cnk 表其中 C n k C n − 1 k − 1 c n − 1 k C_n^kC_{n-1}^{k-1}c_{n-1}^k CnkCn−1k−1cn−1k
三、参考代码
3.1 暴力解
时间复杂度 O ( n 2 ) O(n^2) O(n2) 空间复杂度 O ( 1 ) O(1) O(1)
数据可能会溢出
// 计算cnkk 表示爬 2 个楼梯的个数n 表示楼梯总数 - k
int c(int k,int n){long long int a1,b1;for(int i0;ik;i){a*n-i;b*k-i;}return a/b;
}int climbStairs(int n) {int sum0;for(int i0;2*in;i){sumc(i,n-i);}return sum;
}3.2 动态规划
时间复杂度 O ( n ) O(n) O(n) 空间复杂度 O ( 1 ) O(1) O(1)
const static int max45;
long c[max1][max1];
// dp方法核心是 c[n][k]c[n-1][k-1]c[n-1][k]
void compute_c(){for(int i0;imax;i){ c[i][0]c[i][i]1;}for(int n1;nmax;n){for(int k1;kn;k){c[n][k]c[n-1][k-1]c[n-1][k];}}
}
int climbStairs(int n) {int sum0;compute_c();for(int i0;2*in;i){sumc[n-i][i];}return sum;
}
