一、斐波那契数列

解法一:递归

class Solution {
public:
    int Fibonacci(int n) {
        if(n==1||n==2)
            return 1;
        else
            return Fibonacci(n-1)+Fibonacci(n-2);
    }
};
1
2
3
4
5
6
7
8
9

时间复杂度：O(2^n)每个递归会调用两个递归，因此呈现2的指数增长
空间复杂度：O(n), 递归栈的最大深度

解法二:迭代(推荐)

class Solution {
public:
    int Fibonacci(int n) {
        //从0开始，第0项是0，第一项是1
        if(n <= 1)    
             return n;
         int res = 0;
         int a = 0;
         int b = 1;
         //因n=2时也为1，初始化的时候把a=0，b=1
         for (int i = 2; i <= n; i++){
         //第三项开始是前两项的和,然后保留最新的两项，更新数据相加
             res = (a + b);
             a = b;
             b = res;
         }
        return res;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

时间复杂度：O(n)，其中n为输入的数，n次迭代
空间复杂度：O(1)，常数级变量，没有其他额外辅助空间

解法三:动态规划

• 创建一个长度为n+1的数组，因为只有n+1n才能有下标第n项，我们用它记录前n项斐波那契数列。
• 根据公式，初始化第0项和第1项（题目中是第1项和第2项，本质上一样的）。
• 遍历数组，依照公式某一项等于前两项之和，将数组后续元素补齐，即可得到fib[n]

class Solution {
public:
    int Fibonacci(int n) {
        if(n<=1)
            return n;
        int*fib=new int[n+1];
        fib[0]=0,fib[1]=1;
        for(int i=2;i<=n;i++)
            fib[i]=fib[i-1]+fib[i-2];
        return fib[n];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

时间复杂度：O(n)，一个for循环遍历
空间复杂度：O(n)，创建了一个大小为n+1的动态数组

二、跳台阶

解法一:递归

class Solution {
public:
    int jumpFloor(int number) {
        //这里第0项为1，第1项为1
        if(number <= 1)
            return 1;
        else
            //递归子问题相加
            return jumpFloor(number - 1) + jumpFloor(number - 2);  
    }
};
1
2
3
4
5
6
7
8
9
10
11

时间复杂度：O(2^n),每个递归会调用两个递归，因此呈现2的指数增长
空间复杂度：O(n), 栈空间最大深度为n

解法二:递归优化

• 使用dp数组记录前面的数列值。
• 函数中低于2项的数列，直接返回1。
• 对于当前n，如果dp数组中存在则直接使用，否则递归调用函数计算两个子问题相加。

class Solution {
public:
    //设置全局变量，因为实际问题中没有0，则可用0作初始标识值
    int dp[50] = {0};
    int F(int n){
        if(n <= 1)
            return 1;
        //若是dp中有值则不需要重新递归加一次
        if(dp[n] != 0)   
            return dp[n];
        //若是dp中没有值则需要重新递归加一次
        return dp[n] = F(n - 1) + F(n - 2);
    }
    int jumpFloor(int number) {
        return F(number);
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

时间复杂度：每个数字只算了一次，故为O(n)
空间复杂度：O(n)，栈空间最大深度

解法三:迭代相加(推荐)

• 低于2项的数列，直接返回n。
• 初始化第0项，与第1项分别为0，1.
• 从第2项开始，逐渐按照公式累加，并更新相加数始终为下一项的前两项。

class Solution {
public:
    int jumpFloor(int number) {
        //从0开始，第0项是0，第一项是1
        if(number <= 1)    
            return 1;
        int res = 0;
        int a =1;
        int b = 1;
        //因n=2时也为1，初始化的时候把a=0，b=1
        for(int i = 2; i <= number; i++){
        //第三项开始是前两项的和,然后保留最新的两项，更新数据相加
            res = a + b;
            a = b;
            b = res;
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

时间复杂度：O(n)，其中nnn为输入的数
空间复杂度：O(1)，常数级变量，没有其他额外辅助空间

解法四:动态规划

class Solution {
public:
    int jumpFloor(int number) {
        if(number<=1)
            return 1;
        int*res=new int[number+1];
        res[0]=1,res[1]=1;
        for(int i=2;i<=number;i++)
            res[i]=res[i-1]+res[i-2];
        return res[number];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

时间复杂度：O(n)，遍历了一次长度为n的数组
空间复杂度：O(n)，建立了一个数组辅助

三、最小花费爬楼梯

解法:动态规划

• 可以用一个数组记录每次爬到第i阶楼梯的最小花费，然后每增加一级台阶就转移一次状态，最终得到结果。
• 初始状态） 因为可以直接从第0级或是第1级台阶开始，因此这两级的花费都直接为0.
• 状态转移） 每次到一个台阶，只有两种情况，要么是它前一级台阶向上一步，要么是它前两级的台阶向上两步，因为在前面的台阶花费我们都得到了，因此每次更新最小值即可，转移方程为 dp[i]=min(dp[i−1]+cost[i−1],dp[i−2]+cost[i−2])

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        //dp[i]表示爬到第i阶楼梯需要的最小花费
        vector<int> dp(cost.size() + 1, 0); 
        for(int i = 2; i <= cost.size(); i++)
            //每次选取最小的方案
            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]); 
        return dp[cost.size()];
    }
};

1
2
3
4
5
6
7
8
9
10
11
12

时间复杂度：O(n)，其中n为给定的数组长度，遍历一次数组
空间复杂度：O(n)，辅助数组dp的空间