剑指offer11——动态规划(简单)

剑指 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;
}
};