|
问题分析
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？是引用
当n=1时，只需爬一个台阶，就是一种解法。
当n=2时，可以走两次一层或者走一次2层。
当n=3时，此时你可能在第一层或者第二层，当在第一层时相当于你在第0层准备去往第二层，当在第二层时相当于你在第0层准备去往第1层。
以此类推。
1.递归调用
int climbStairs(int n)
{
if(n==1||n==2){
return n;
}else{
return climbStairs(n-1)+climbStairs(n-2);
}
}
时间复杂度：（2^n) 空间复杂度：（n） 运用了递归耗时较久。
2.优化递归调用
在方法一的递归中，实际上在递归遍历的过程中经过了许多重复的结点，因此我们可以利用一个数组存储已经遍历过的结点，降低时间复杂度。
int climStairsMemo(int n,int *memo){
if(memo[n]>0){
return memo[n];
}
if(n==1||n==2){
memo[n]=n;
}else{
memo[n]=climStairsMemo(n-1,memo)+climStairsMemo(n-2,memo);
}
return memo[n];
}
int climbStairs(int n)
{
int* memo=(int*)malloc((n+1)*sizeof(int));
for(int i=0;i |