题目
小乐爬楼梯,一次只能上1级或者2级台阶。楼梯一共有n级台阶,请问总共有多少种方法可以爬上楼?
解析
这道题虽然是一道编程题,但实际上更是一道数学题,着重考察应聘者的逻辑思维能力和分析解决问题的能力。
当楼梯只有1级时,只有1种方法可以上楼。
当楼梯有2级时,有两种方法可以上楼:一次跨1级,或者一次跨2级。
对于大于2级的楼梯,我们可以选择从第n-1级跨1级,或者从第n-2级跨2级。所以,对于n级楼梯的方法数为:f(n) = f(n-1) + f(n-2)。
这种思考问题的方法就是递归的思想。下面,我们给出了用递归函数求解这道题的示例代码。
fn calc_upstairs_count(steps: u32) -> u32 {
match steps {
0 => 0,
1 => 1,
2 => 2,
_ => calc_upstairs_count(steps - 1) + calc_upstairs_count(steps - 2),
}
}
fn main() {
println!("{}", calc_upstairs_count(0));
println!("{}", calc_upstairs_count(1));
println!("{}", calc_upstairs_count(2));
println!("{}", calc_upstairs_count(3));
println!("{}", calc_upstairs_count(4));
println!("{}", calc_upstairs_count(5));
}
可以看到,采用递归实现的代码非常简洁。但递归算法也有其缺点:一是递归的层级较多时,可能会导致堆栈溢出;二是递归算法的时间复杂度一般较高,效率较低。具体到本题,因为每次递归都可能产生两种选择,故时间复杂度为O(2^n)。计算n级台阶和n-1级台阶的方法数时,都会去计算n-2级台阶的方法数,从而导致大量的重复计算。
有没有更好的解决问题的方法呢?答案是肯定的,我们可以通过动态规划算法来尝试一下。
我们可以使用一个数组dp来存储每级楼梯的方法数,初始条件为:dp[1] = 1, dp[2] = 2。
对于大于2级的楼梯,我们可以从第n-1级跨1级到达第n级,或者从第n-2级跨2级到达第n级。所以,dp[n] = dp[n-1] + dp[n-2]。
这样,我们可以通过一次遍历,计算出所有楼梯级数的方法数。这种方法的时间复杂度为O(n),空间复杂度也为O(n)。下面,我们给出了用动态规划算法求解这道题的示例代码。
fn calc_upstairs_count(steps: u32) -> u32 {
let mut dp = vec![0; (steps + 1) as usize];
if steps >= 1 {
dp[1] = 1;
}
if steps >= 2 {
dp[2] = 2;
}
for i in 3..=(steps as usize) {
dp[i] = dp[i - 1] + dp[i - 2];
}
dp[steps as usize]
}
fn main() {
println!("{}", calc_upstairs_count(0));
println!("{}", calc_upstairs_count(1));
println!("{}", calc_upstairs_count(2));
println!("{}", calc_upstairs_count(3));
println!("{}", calc_upstairs_count(4));
println!("{}", calc_upstairs_count(5));
}
总结
通过这道题,我们学会了用递归算法和动态规划算法来编程处理问题。递归算法的时间复杂度较高,动态规划算法的时间复杂度较低。
学习了上面的示例代码后,你真的理解递归算法和动态规划算法了吗?我们为你留了一些课后的拓展作业,快来试一试吧!
1、小乐爬楼梯,一次只能上1级台阶,或者2级台阶,或者3级台阶。楼梯一共有n级台阶,请问总共有多少种方法可以爬上楼?
2、有长宽分别为1x1和1x2的小格子,现在要用这两种小格子拼接成1xN的大格子。请编写一个方法来计算一共有多少种拼接方案,N作为方法的唯一参数,返回值为拼接方案数。