目录

  • 爬楼梯
  • 买卖股票的最佳时机

爬楼梯

题目描述

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
注意:给定 n 是一个正整数。

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
示例 1:
输入: 2
输出: 2
解释: 有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶

示例 2:
输入: 3
输出: 3
解释: 有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

题解

动态规划

对于第k层,可能是一步上来的,也可能是两步上来的。如果是跳1步上来的,则方法数与到k-1层相同,如果是跳2步上来的,则方法数与到k-2层相同。
因此有$f(k) = f(k-1) + f(k-2)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
def climbStairs(self, n: int) -> int:
if n == 1:
return 1
dp = [0] * (n+1)

# 设置边界
dp[0] = 0
dp[1] = 1
dp[2] = 2
for i in range(3, n+1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]

买卖股票的最佳时机

题目描述

给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润,返回 0 。

示例

1
2
3
4
5
6
7
8
9
10
示例 1:
输入:[7,1,5,3,6,4]
输出:5
解释:在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格;同时,你不能在买入前卖出股票。

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

题解

动态规划

对于每一天,有两种可能,持有股票和不持有股票。
如果持有股票,那么又有两种情况,1)前一天就持有;2)今天刚买入。
如果不持有股票,对应两种情况:1)之前一直没买入;2)今天刚卖出。
对于每一天的收益,只与前一天的收益有关,用两个变量hold 和 nohold分别记录前一时刻 持有 和 不持有 股票的最大收益即可。 注意点是全程只能买卖一次股票。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if len(prices) == 0:
return 0

# 初始化边界值
hold = -prices[0] # 第0天就持有的收益
nohold = 0 # 第0天不持有的收益
for i in range(1, len(prices)):
hold = max(hold, -prices[i]) # 第i天持有的收益,就是对应两种情况的收益最大值
nohold = max(nohold, hold+prices[i]) # 第i天不持有的收益,就是对应两种情况的收益最大值
return nohold # 最后利润最大,一定是卖出去的