121. 买卖股票的最佳时机
股票问题详解
1、状态：有两种状态：持有或者没有股票。每天的状态是其中之一。
2、当天是否持有股票的最大利润 = max ( 前一天是否持有股票的最大利润, 今天是否买卖股票所造成的利润）
var maxProfit = function(prices) {
let n = prices.length;
// 定义一个二维数组
let dp = new Array(n).fill(new Array(2));
// dp[i][j]表示第i天股票状态为j时的最大利润（现金数）
// 初始化第1天时的利润,不买入股票就是0，买入股票就是负值
dp[0][0] = 0;
dp[0][1] = -prices[0];
// 从第二天算起
for(let i=1;i<n;i++){
// 第i天手里没有股票：第i-1天本来就没有 / 第i-1天有，但是第i天卖出了-- 取其中的最大值就是第i天的状态
dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]+prices[i])
// 第i天手里有股票：第i-1天本来就有 / 第i-1天没有，但是第i天买了(就是负值)-- 取其中的最大值就是第i天的状态
dp[i][1] = Math.max(dp[i-1][1],-prices[i])
}
// 因为最后还是要卖出的，所以最大的利润是没有股票的状态
return dp[n-1][0];
};
122. 买卖股票的最佳时机 II
var maxProfit = function(prices) {
const n = prices.length
// dp[i][j]表示第i天股票状态为j时的最大利润，j有两种状态
const dp = new Array(n).fill().map(()=>new Array(2).fill())
// 第一天的情况
dp[0][0] = 0 // 第一天不持有
dp[0][1] = -prices[0] // 第一天持有，就是买东西了，利润为负
// 从第二天开始
for(let i=1; i<n; i++){
// 不持有
dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]+prices[i])
// 第i天持有：第i-1天有 / 第i-1天没有，第i天买入了。但是此时的利润不是负数，因为之前可能进行了买卖，有存款在。
dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]-prices[i])
}
// 最后要卖出
return dp[n-1][0]
};
123. 买卖股票的最佳时机 III
var maxProfit = function(prices) {
const n = prices.length
// dp[i][j]表示第i天股票状态为j时的最大利润，j有4种状态。第一次持有，第一次不持有，第二次持有，第二次不持有
const dp = new Array(n).fill().map(()=>new Array(4).fill(0))
// 第1天持有
dp[0][0] = -prices[0]
dp[0][2] = -prices[0]
// 从第二天开始
for(let i=1; i<n; i++){
// 第一次持有
dp[i][0] = Math.max(dp[i-1][0],-prices[i])
// 第一次不持有
dp[i][1] = Math.max(dp[i-1][1],dp[i][0]+prices[i])
// 第二次持有
dp[i][2] = Math.max(dp[i-1][2],dp[i][1]-prices[i])
// 第二次不持有
dp[i][3] = Math.max(dp[i-1][3],dp[i][2]+prices[i])
}
// 最后要卖出
return dp[n-1][3]
};