Leetcode之动态规划（DP）专题-188. 买卖股票的最佳时机 IV（Best Time to Buy and Sell Stock IV）
2024-08-29 19:28:01
Leetcode之动态规划（DP）专题-188. 买卖股票的最佳时机 IV（Best Time to Buy and Sell Stock IV）
股票问题：
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: [2,4,1], k = 2
输出: 2
解释: 在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。
示例 2:
输入: [3,2,6,5,0,3], k = 2
输出: 7
解释: 在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。
限制了交易次数的股票问题。
DP含义：
dp[i][0][k]表示在第i天的时候，手上没有股票，最大限制交易次数为k次的最大利润。
dp[i][1][k]表示在第i天的时候，手上有股票，最大限制交易次数为k次的最大利润。
解释：
一、在第i天，手上没有股票，有两种原因：
1、第i-1天的时候就没有，第i天休息了，什么都没干
2、第i-1天的时候有股票，但是第i天把股票卖了
二、在第i天，手上有股票，有两种原因：
1、第i-1天的时候就没有，第i天啥都没干
2、第i-1天的时候没有股票，第i天买入了一支 另外注意，如果k>prices.length/2的时候，k就变成无限制次数的交易了。
那就可以用贪心or不限制k次数的dp来求解。
不然会爆内存。
class Solution {
public int maxProfit(int k, int[] prices) {
if(prices==null || prices.length==0) return 0;
if(k>prices.length/2){
return maxProfit(prices);
}
int[][][] dp = new int[prices.length][2][k+1];
for (int i = 0; i < k+1; i++) {
dp[0][0][i] = 0;
dp[0][1][i] = -prices[0];
}
for (int i = 1; i < prices.length; i++) {
for (int k1 = 1; k1 <= k; k1++) {
dp[i][0][k1] = Math.max(dp[i-1][0][k1],dp[i-1][1][k1]+prices[i]);
dp[i][1][k1] = Math.max(dp[i-1][1][k1],dp[i-1][0][k1-1]-prices[i]);
}
}
return dp[prices.length-1][0][k];
}
public int maxProfit(int[] prices) {
if(prices==null || prices.length==0) return 0;
int[][] dp = new int[prices.length][2];
dp[0][0] = 0;
dp[0][1] = -prices[0];
for (int i = 1; i < prices.length; i++) {
dp[i][0] = Math.max(dp[i-1][1]+prices[i],dp[i-1][0]);
dp[i][1] = Math.max(dp[i-1][0]-prices[i],dp[i-1][1]);
}
return dp[prices.length-1][0];
}
}
最新文章
- java多线程wait notify join
- github的使用步骤及体会
- Silverlight中的TabControl如何绑定数据？重写tabcontrol和tabItem 解决绑定友好问题。可以绑定对象集合
- NDK编译FreeImage
- JavaScript navigator 对象(转)
- acm 20140825
- 《linux性能及调优指南》
- Stimulsoft Reports报表工具
- 状态开关按钮（ToggleButton）及按钮(Swich)的使用
- (转)syslog日志等级
- Json.Net介绍及实例
- VisualStudioOnline协同工作流程
- webpy 开发环境搭建问题之Mysql-python安装
- Unity 3D Framework Designing(9)——构建统一的 Repository
- AJAX做增删改查详细！
- Codeforces Round #419 (Div. 2)
- 中点Bresenham画圆
- 2393Cirno的完美算数教室 容斥
- SpringBoot集成rabbitmq（二）
- [Reinforcement Learning] Value Function Approximation