#Java #动态规划 #
Feeling and experiences：
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成?两笔?交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例?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 。
升级版
可以进行两次买卖，但是不能同时持有两张股票
class Solution {
public int maxProfit(int[] prices) {
//可以进行两次买卖，但是不能同时持有两张股票
//定义物种状态
//1.不做操作 2.第一次买入 3.第一次卖出 4.第二次买入 5.第二次卖出
//创建dp数组
int [][]dp = new int[prices.length][5]; //5种状态
//初始化
//第一次买入
dp[0][1] = -prices[0];
//第二次买入
dp[0][3] = -prices[0];
for (int i = 1; i < prices.length; i++) {
dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
dp[i][4] = Math.max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
}
return dp[prices.length-1][4];
}
}1. 不做操作（dp[i][0]）：
这是一个初始状态，通常我们不需要显式计算它，因为这种状态的利润始终为?0。
2. 第一次买入（dp[i][1]）：
? 要么我们在第?i?天买入股票，此时利润为?-prices[i]。
? 要么我们在之前已经买过了，即?dp[i-1][1]。
最大利润为两者中的最大值。
3. 第一次卖出（dp[i][2]）：
? 要么我们在第?i?天卖出股票，此时利润为?dp[i-1][1]?+?prices[i]。
? 要么我们在之前已经卖过了，即?dp[i-1][2]。
同样，取最大值。
4. 第二次买入（dp[i][3]）：
? 要么我们在第?i?天再次买入股票，此时利润为?dp[i-1][2]?-?prices[i]。
? 要么我们之前已经买过了，即?dp[i-1][3]。
取最大值。
5. 第二次卖出（dp[i][4]）：
? 要么我们在第?i?天卖出股票，此时利润为?dp[i-1][3]?+?prices[i]。
? 要么我们之前已经卖过了，即?dp[i-1][4]。
取最大值。
?
还有一更为简便的写法：
class Solution {
public int maxProfit(int[] prices) {
int dp1 = -prices[0];
int dp2 = 0;
int dp3 = -prices[0];
int dp4 = 0;
for (int i=1; i<prices.length; i++) {
dp1 = Math.max(-prices[i], dp1);
dp2 = Math.max(dp1 + prices[i], dp2);
dp3 = Math.max(dp2 - prices[i], dp3);
dp4 = Math.max(dp3 + prices[i], dp4);
}
return dp4;
}
}? 考虑每个状态的实际含义：
? 第一次买入（buy1）：这意味着我们在第一天或之前买入股票。因为我们还没有进行任何交易，所以这个值应该是负的第一天的股票价格（表示成本）。
? 第一次卖出（sell1）：在第一天结束时，我们不可能已经卖出股票，因此这个状态的初始利润应该是?0。
? 第二次买入（buy2）：这代表在第一次交易完成后的第二次买入。在第一天，即使我们假设在开盘时卖出再买入，这个值也应该是负的（因为我们至少要支付第一天的股票价格）。
? 第二次卖出（sell2）：和第一次卖出一样，我们在第一天结束时不可能已经完成第二次卖出，所以这个状态的利润也应该是?0。
?
给你一个整数数组?prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1：
输入：k = 2, prices = [2,4,1] 输出：2 解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。
可以进行x次交易
class Solution {
public int maxProfit(int k, int[] prices) {
if (prices == null || prices.length == 0) return 0;
// 如果 k 大于等于 prices.length / 2，则等同于无限次交易
if (k >= prices.length / 2) {
int profit = 0;
for (int i = 1; i < prices.length; i++) {
if (prices[i] > prices[i - 1]) {
profit += prices[i] - prices[i - 1];
}
}
return profit;
}
// dp 数组
int[][] dp = new int[prices.length][2 * k + 1];
// 初始化买入状态
for (int i = 1; i < 2 * k; i += 2) {
dp[0][i] = -prices[0];
}
// 动态规划填表
for (int i = 1; i < prices.length; i++) {
for (int j = 0; j < 2 * k - 1; j += 2) {
// 处理买入状态
dp[i][j + 1] = Math.max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i]);
// 处理卖出状态
dp[i][j + 2] = Math.max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i]);
}
}
return dp[prices.length - 1][2 * k];
}
}
1. 买入状态（当?j?是奇数时）：
在买入状态下，对于每个奇数状态?j（表示第?(j+1)/2?次买入）：
这里，dp[i-1][j]?表示前一天保持同样状态的最大利润（即没有交易），而?dp[i-1][j-1]?-?prices[i]?表示前一天处于上一个状态（即上一次的卖出状态）并在第?i?天买入股票。
2. 卖出状态（当?j?是偶数时）：
在卖出状态下，对于每个偶数状态?j（表示第?j/2?次卖出）：
这里，dp[i-1][j]?表示前一天保持同样状态的最大利润（即没有交易），而?dp[i-1][j-1]?+?prices[i]?表示前一天处于上一个状态（即上一次的买入状态）并在第?i?天卖出股票。?
?
桃李春风一杯酒，
江湖夜雨十年灯。
Fighting！