剑指 Offer 10- I. 斐波那契数列

难度 简单

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：

1
2
F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例 1：

1
2
输入：n = 2
输出：1

示例 2：

1
2
输入：n = 5
输出：5

提示：

  • 0 <= n <= 100

思路与题解

  1. **状态定义：**F[i]为第i个斐波那契数列的数字

  2. 转移方程：$F[i] = F[i-1]+F[i-2]$

  3. 初始状态：$F[0]=0;F[1]=1$

  4. **计算顺序：**从0开始向目标迭代

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int fib(int n) {
        int *F = new int[n+2];
        
        F[0] = 0;
        F[1] = 1;

        int i;
        for(i = 2; i <= n ; i++)
            F[i] = ( F[i-1] + F[i-2] ) % 1000000007;;

        return F[n] ;
    }
};

剑指 Offer 10- II. 青蛙跳台阶问题

难度 简单

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例 1：

1
2
输入：n = 2
输出：2

示例 2：

1
2
输入：n = 7
输出：21

示例 3：

1
2
输入：n = 0
输出：1

提示：

  • 0 <= n <= 100

注意：本题与主站 70 题相同：https://leetcode-cn.com/problems/climbing-stairs/

思路与题解

由于最后一级台阶只能从倒数第二级和倒数第三级跳上来，所以
跳上第n个台阶的方法数量 = 跳上第n-1个台阶的方法数量 + 跳上第n-2个台阶的方法数量
所以本题和斐波那契数列的题是一致的，只不过初始条件由$F(0) = 0,F (1) = 1,F(2) = 1$变成了$F(0) = 1,F (1) = 1,F(2) = 2$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*
    转移方程：F[n] = F[n-1]+F[n-2]
*/

class Solution {
public:
    int numWays(int n) {
        if(n == 0 || n == 1)return 1;
        int a,b,tmp,i,sum;
        a = 1;
        b = 1;
        for(i = 2; i <= n; i++)
        {
            sum = (a + b) % 1000000007;
            tmp = b;
            b = sum;
            a = tmp;
        }
        return sum;
    }
};

剑指 Offer 63. 股票的最大利润

难度 中等

假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？

示例 1:

1
2
3
4
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。

示例 2:

1
2
3
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

限制：

1
0 <= 数组长度 <= 10^5

思路与题解

假设输入为[7,1,5,3,6,4]

分解问题并缩小为六个子问题：

1
2
3
4
5
6
7
8
9
10
11
[7,1,5,3,6,4] -> max = 5

[7,1,5,3,6] -> max = 5

[7,1,5,3] -> max = 4

[7,1,5] -> max = 4

[7,1] -> max = 0

[7] -> max = 0

则

$$
F[n] = max( F[n-1], max(prices[n] - prices[i]))
$$

即 F[n] 为过去的最高利润 与 在第n日卖出时利润更高者

但是这里我用了两个循环来解，把时间复杂度整高了。。。导致了超时。。。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/*
    假设输入为[7,1,5,3,6,4]
    分解问题并缩小为六个子问题：
    [7,1,5,3,6,4] -> max = 5
    [7,1,5,3,6] -> max = 5
    [7,1,5,3] -> max = 4
    [7,1,5] -> max = 4
    [7,1] -> max = 0
    [7] -> max = 0
    F[n] = max( F[n-1], max(nums[n] - nums[i]))
    即 F[n] 为过去的最高利润 与 在第n日卖出时利润更高者
*/
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if( prices.empty() ) return 0; 
        int n = prices.size();
        int *F = new int[n];

        F[0] = 0;

        int i,j;
        for( i = 1; i < n; i++ )
        {
            F[i] = F[i-1];
            for(j = 0;j < i; j++)
            {
                if(prices[i] - prices[j] > F[i] )
                    F[i] = max(F[i-1], prices[i] - prices[j]);
            }
        }
        return F[n-1];
    }
};

思路2

大佬的思路：

大佬的转移方程写的比我的清楚：
$$
前i日最大利润=\max(前(i−1)日最大利润,第i日价格−前i日最低价格)\
dp[i]=\max(dp[i−1],prices[i]−\min(prices[0:i]))
$$
时间复杂度降低： 前 $i$ 日的最低价格 $min(prices[0:i]) $时间复杂度为 $O(i)$ 。而在遍历 $prices$时，可以借助一个变量（记为成本 $cost$ ）每日更新最低价格。优化后的转移方程为：
$$
dp[i]=\max(dp[i−1],prices[i]−\min(cost,prices[i]))
$$
空间复杂度降低： 由于$ dp[i]$ 只与 $dp[i - 1] , prices[i] , cost$ 相关，因此可使用一个变量（记为利润 $profit$ ）代替 $dp $列表。优化后的转移方程为：
$$
profit = \max(profit, prices[i] - \min(cost, prices[i])
$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/*
    假设输入为[7,1,5,3,6,4]
    分解问题并缩小为六个子问题：
    [7,1,5,3,6,4] -> max = 5
    [7,1,5,3,6] -> max = 5
    [7,1,5,3] -> max = 4
    [7,1,5] -> max = 4
    [7,1] -> max = 0
    [7] -> max = 0
    F[n] = max( F[n-1], max(nums[n] - nums[i]))
    即 F[n] 为过去的最高利润 与 在第n日卖出时利润更高者
*/
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        //Special case
        if( prices.empty() ) return 0;

        //Variable declaration
        int n,cost,profit;
        
        //Initialize
        n = prices.size();
        profit = 0;
        cost = prices[0];

        //Main loop
        for(int i = 1; i < n; i++ )
        {
            cost = min(cost,prices[i]);
            profit = max(profit, prices[i] - cost);
        }
        return profit;
    }
};