没有合适的资源?快使用搜索试试~ 我知道了~
1、第 i 天不做任何交易,那么 f[i][k] = f[i - 1][k] 2、第 i 天做交易,卖出手中的股票,那么 f[i][k] = f[j][k -
资源详情
资源评论
资源推荐
力扣500题刷题笔记
188. 买卖股票的最佳时机 IV *
题目
给定一个整数数组 prices ,它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
示例 1:
示例 2:
提示:
0 <= k <= 100
0 <= prices.length <= 1000
0 <= prices[i] <= 1000
思路
(动态规划)
首先,有个比较特殊的前提,若一共有 n 天,则最多买卖 n/2 次(因为买卖在同一天收益得 0 ,买卖在
不同天才会有收益),因此如果 k > n/2 的话,可以直接令 k = n/2 。
输入:k = 2, prices = [2,4,1]
输出:2
解释:在第 1 天 (股票价格 = 2) 的时候买入,在第 2 天 (股票价格 = 4) 的时候卖出,这笔交易
所能获得利润 = 4-2 = 2 。
1
2
3
输入:k = 2, prices = [3,2,6,5,0,3]
输出:7
解释:在第 2 天 (股票价格 = 2) 的时候买入,在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易
所能获得利润 = 6-2 = 4 。
随后,在第 5 天 (股票价格 = 0) 的时候买入,在第 6 天 (股票价格 = 3) 的时候卖出, 这
笔交易所能获得利润 = 3-0 = 3 。
1
2
3
4
常规思路
状态表示: f[i][k] 表示考虑前 i 天,完成了 k 笔交易的最大收益。(买卖各一次为一次交易)
状态计算:
对于 i 天,我们有两种选择:
1、第 i 天不做任何交易,那么 f[i][k] = f[i - 1][k] 。
2、第 i 天做交易,卖出手中的股票,那么 f[i][k] = f[j][k - 1] + p[i] - p[j] 。( 0 <= j
<= i )
由于我们要求的是最大收益,因此不考虑在第 i 天买入股票,不然会使收益变低。如果我们在第 i 天卖
出,那么当天的收益就是枚举买入股票的日期 j ,计算 p[i] - p[j] ,再加上考虑前 j 天,最多完成 j
- 1 笔交易的最大收益。
状态DP
状态表示:
1、 f[i][j] 表示考虑前 i 天,恰好交易了 j 次股票,且当前手中不持有股票的最大收益(已卖
出手中股票)。
2、 g[i][j] 表示考虑前 i 天,恰好交易了 j 次股票,且当前手中持有股票的最大收益(未卖出
手中股票)。
状态计算:
1、 f[i][j] = max(f[i - 1][j]), g[i - 1][j - 1] + prices[i]
2、 g[i][j] = max(g[i−1][j], f[i−1][j] − prices[i])
c++代码
int f[10001], g[10001];
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
int INF = 1e8;
int n = prices.size();
k = min(k, n / 2);
memset(f, -0x3f, sizeof f);
1
2
3
4
5
6
7
8
9
java代码
134. 加油站
题目
在一条环路上有 N 个加油站,其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车,从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你
从其中的一个加油站出发,开始时油箱为空。
如果你可以绕环路行驶一周,则返回出发时加油站的编号,否则返回 -1 。
说明:
如果题目有解,该答案即为唯一答案。
输入数组均为非空数组,且长度相同。
输入数组中的元素均为非负数。
示例 1:
示例 2:
memset(g, -0x3f, sizeof g);
f[0] = 0;
int res = 0;
for (int i = 1; i <= n; i ++ )
for (int j = k; j >= 0; j -- ) {
g[j] = max(g[j], f[j] - prices[i - 1]);
if (j) f[j] = max(f[j], g[j - 1] + prices[i - 1]);
}
for (int i = 1; i <= k; i ++ ) res = max(res, f[i]);
return res;
}
};
10
11
12
13
14
15
16
17
18
19
20
21
1
输入:
gas = [1,2,3,4,5]
cost = [3,4,5,1,2]
输出: 3
解释:
从 3 号加油站(索引为 3 处)出发,可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 4 号加油站,此时油箱有 4 - 1 + 5 = 8 升汽油
开往 0 号加油站,此时油箱有 8 - 2 + 1 = 7 升汽油
开往 1 号加油站,此时油箱有 7 - 3 + 2 = 6 升汽油
开往 2 号加油站,此时油箱有 6 - 4 + 3 = 5 升汽油
开往 3 号加油站,你需要消耗 5 升汽油,正好足够你返回到 3 号加油站。
因此,3 可为起始索引。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
思路
假如从第 i 个站开始走,没法走一圈回来,而是最多走到第 j 个站,那么从 i...j 之间的一个站点 k 开
始走,也没有可能超过 j 这个站,因为从 i 走到 k 的时候是有 >=0 的剩余油量的,但是从第 k 个站出发
的话就没有这些油量了,所以更不可能走超过 j 。
因此,如果没法到达第 j 个站,那么我们可以直接排除 i + 1, i + 2,,,j 这些不合法加油站,直接从
j+1 加油站开始作为下一次的起点。
时间复杂度分析:
c++代码
输入:
gas = [2,3,4]
cost = [3,4,3]
输出: -1
解释:
你不能从 0 号或 1 号加油站出发,因为没有足够的汽油可以让你行驶到下一个加油站。
我们从 2 号加油站出发,可以获得 4 升汽油。 此时油箱有 = 0 + 4 = 4 升汽油
开往 0 号加油站,此时油箱有 4 - 3 + 2 = 3 升汽油
开往 1 号加油站,此时油箱有 3 - 3 + 3 = 3 升汽油
你无法返回 2 号加油站,因为返程需要消耗 4 升汽油,但是你的油箱只有 3 升汽油。
因此,无论怎样,你都不可能绕环路行驶一周。
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int n = gas.size();
for(int i = 0; i < n; ){// 枚举每个起点
int left = 0, j = 0; //剩余油量, 每次走的站点数
for(; j < n; j++){
int k = (i + j) % n; //下一个要到达的站点
left += gas[k] - cost[k];
if(left < 0) break; //当前起点不合法
}
if(j == n) return i; //返回合法起点
1
2
3
4
5
6
7
8
9
10
11
12
剩余25页未读,继续阅读
ShepherdYoung
- 粉丝: 32
- 资源: 337
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0