当前位置 博文首页 > Inmaturity_7的博客：动态规划的四个最佳实践--Leecode的四个股
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
（题目来源：力扣（LeetCode））
示例 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 <= prices.length <= 105
0 <= prices[i] <= 104
package com.lxf.dp;
public class MaxProfit1 {
public int maxProfit(int prices[]) {
//最大收益
int maxProfit=0;
//股票最小价格
int minPrice=Integer.MAX_VALUE;
for (int i = 0; i < prices.length; i++) {
if(minPrice>prices[i]){
//如果当前价格比当前最小价格还要小的时候，我们直接换成当前价格
//这样保证了最低价格是全局最小，而且是提前确定的
//也就是提前确定好最低价格，再考虑卖出
minPrice=prices[i];
}else if(prices[i]-minPrice>maxProfit){
//如果当前卖出的收益最大则，替换之
maxProfit=prices[i]-minPrice;
}
}
return maxProfit;
}
}
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
(题目来源：力扣（LeetCode）)
示例 1:
输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
示例 2:
输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
示例 3:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
提示：
1 <= prices.length <= 3 * 10 ^ 4
0 <= prices[i] <= 10 ^ 4
package com.lxf.dp;
public class MaxProfit2 {
/**
* 这里就是求升序高度差，所以用贪心更好些
* 我们现在主要是针对dp
* @param prices
* @return
*/
public int maxProfit(int[] prices) {
//有股票时最大的收益(从第一个股票开始，我们刚开始肯定是负数)
int yP=-prices[0];
//没有股票时的最大收益(第一次不买股票以及卖出股票时的收益)
int nP=0;
for (int i = 0; i < prices.length; i++) {
//没有股票=上一次的没有股票的最大收益和本次卖出股票的最大收益取最大值
nP=Math.max(nP,yP+prices[i]);
//有股票=上一次的有股票的最大收益和本次卖进股票的最大收益取最大值
yP=Math.max(yP,nP-prices[i]);
}
//最后肯定是没有持有股票的收益最大，因为最后一次是升序那肯定卖出了
//如果最后一次是降序那就没必要考虑这一段降序了，在前一段升序中卖出即可
return nP;
}
}
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
（题目来源：力扣（LeetCode））
示例 1:
输入：prices = [3,3,5,0,0,3,1,4]
输出：6
解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。
示例 2：
输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
示例 3：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这个情况下, 没有交易完成, 所以最大利润为 0。
示例 4：
输入：prices = [1]
输出：0
提示：
1 <= prices.length <= 105
0 <= prices[i] <= 105
package com.lxf.dp;
public class maxProfit3 {
public int maxProfit(int[] prices) {
//该题dp的五个状态：
//dp0:一直不买,所以等于0
//dp1：买入一次(已经买入，或者没买入过，这次买入)。这里用buy1表示
//dp2：卖出一次(已经买出一次，或者没买出过，这次买出)。这里用sell1表示
//dp3：买入两次(已经买入两次，或者只买入过一次且卖出过一次，这次买入第二次)。这里用buy2表示
//dp3：卖出两次(已经卖出两次，或者买进两次卖出一次，这次卖出第二次)。这里用sell2表示
int buy1=-prices[0],sell1=0,buy2=-prices[0],sell2=0;
for (int i = 1; i < prices.length; i++) {
//第一次买入=Math.max(dp1,dp0-prices[i]);
//即：
buy1=Math.max(buy1,-prices[i]);
//第一次买出=Math.max(dp2,dp1+prices[i]);
//即：
sell1=Math.max(sell1,buy1+prices[i]);
//第二次买入=Math.max(dp3,dp2-prices[i]);
//即：
buy2=Math.max(buy2,sell1-prices[i]);
//第三次买入=Math.max(dp4,dp3+prices[i]);
//即：
sell2=Math.max(sell2,buy2+prices[i]);
}
return sell2;
}
}
给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
（题目来源：力扣（LeetCode））
示例 1：
输入：k = 2, prices = [2,4,1]
输出：2
解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。
示例 2：
输入：k = 2, prices = [3,2,6,5,0,3]
输出：7
解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。
提示：
0 <= k <= 100
0 <= prices.length <= 1000
0 <= prices[i] <= 1000
参考题解：java动态规划，简单易懂
package com.lxf.dp;
public class MaxProfit4 {
public int maxProfit(int k, int[] prices) {
//1、定义状态
//dp[i][0][m] 第i天手里没股票，一共完成了m次交易
//dp[i][1][m] 第i天手里有股票，一共完成了m次交易
//2、状态方程
//dp[i][0][m] = Max(dp[i - 1][0][m], dp[i - 1][1][m - 1] + prices[i])
//dp[i][1][m] = Max(dp[i - 1][1][m], dp[i - 1][0][m] - prices[i])
if (prices.length < 2) return 0;
//dp三维数组
int[][][] dp = new int[prices.length][2][k + 1];
//给所有的第1天有股票的状态赋值
for (int i = 0; i < k; i++) {
dp[0][1][i] = -prices[0];
}
for (int i = 1; i < prices.length; i++) {
//给第i天有股票没有进行过交易的状态赋值：
dp[i][1][0] = Math.max(dp[i - 1][1][0], - prices[i]);
for (int j = 1; j <= k; j++) {
//第i天手里没股票，一共完成了j次交易
dp[i][0][j] = Math.max(dp[i - 1][0][j], dp[i - 1][1][j - 1] + prices[i]);
//第i天手里有股票，一共完成了j次交易
dp[i][1][j] = Math.max(dp[i - 1][1][j], dp[i - 1][0][j] - prices[i]);
}
}
return dp[prices.length - 1][0][k];
}
}
