简单算法学习--股票六杰题型

// 通过代码来详细解释

// 这类题型 主要思路是 dp[i 天数][k 交易次数][0 | 1 是否持有]
// 我们最终要求的可获得的最大收益就是 dp[n - 1][k][0]，代表最后一天将股票卖出后的最大收益
// 所以一切的情况都归类如下：

// 今天手中没有持有股票，有两种可能：
// 1. 昨天没有持有，今天选择不操作。 对应: dp[i - 1][k][0]
// 2. 昨天持有，今天卖出了，所以今天没有股票了。对应: dp[i - 1][k][1] + prices[i]
// dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i])

// 今天手中持有股票，有两种可能：
// 1. 昨天手中持有股票，今天选择不操作。对应: dp[i - 1][k][1]
// 2. 昨天没有持有股票，今天买入了。对应: dp[i - 1][k - 1][0] - prices[i]
// dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i])

//很显然，卖出股票利润增加，买入股票利润减少。因为每次交易包含两次成对的操作，买入和卖出。
// 所以只有买入的时候需要将 k - 1，那么最大利润就是上面这两种可能性中的最大值。

const maxProfit = function(prices) {
    const n = prices.length; // 获取交易长度
    let price_in = -prices[0];
    let price_out = 0;


    for (let i = 1; i < n; i++) {
        // 这一步是因为我们的天数是固定的（只能 i - 1 到 i）我们的交易次数是固定的（只有1次 k = 1） 所以我们可以省略
        price_out = Math.max(price_out, price_in + prices[i])
        // 因为我们交易后就不能再次交易，所以买入的那次一定是从无到有  dp[i - 1][1 - 1][0] = dp[i - 1][0][0]一定为0
        price_in = Math.max(price_in, -prices[i])
    }

    return price_out;
} 

// 这道题可以配合第5题看，学会冷冻期

// 继续公式
const maxProfit = function(prices) {

    // 因为可以交易无数次所以k降纬
    const n = prices.length;

    let price_in = -prices[0];
    let price_out = 0;

    for (let i = 1; i < n; i++) {
        price_out = Math.max(price_out, price_in + prices[i])
        price_in = Math.max(price_in, price_out - prices[i])
    }

    return price_out;
}

const maxProfit = function(prices) {
    let n = prices.length
    let dp_i10 = 0
    let dp_i11 = -prices[0]
    let dp_i20 = 0
    let dp_i21 = -prices[0]
    for (let i = 1; i < n; i++) {
        dp_i20 = Math.max(dp_i20, dp_i21 + prices[i])
        // 这里可以让我们理解到，dp_i21的最大值是第二次操作没卖还是第一次操作刚卖出，和i20无关
        dp_i21 = Math.max(dp_i21, dp_i10 - prices[i])
        dp_i10 = Math.max(dp_i10, dp_i11 + prices[i])
        dp_i11 = Math.max(dp_i11, -prices[i])
    }
    return dp_i20
}

const maxProfit = function(k, prices) {
    let n = prices.length
    const maxProfit2 = function(prices) {
        let profit_out = 0
        let profit_in = -prices[0]
        for (let i = 1; i < n; i++) {
            profit_out = Math.max(profit_out, profit_in + prices[i])
            profit_in = Math.max(profit_in, profit_out - prices[i])
        }
        return profit_out
    }

    // 如果长度是操作的2倍，则相当于可以操作无限次（用不完操作天数）
    if (k > n / 2) {
        return maxProfit2(prices)
    }


    let profit = new Array(k)
    // 初始化买入卖出时的利润，将每次交易买入、卖出时的利润放在一个对象中，实现降维
    for (let j = 0; j <= k; j++) {
        profit[j] = {
            profit_in: -prices[0],
            profit_out: 0
        }
    }
    for (let i = 1; i < n; i++) {
        for (let j = 1; j <= k; j++) {
            // 天数降纬，只统计第j次操作的大小
            profit[j] = {

                // 卖出的最大利润是一只空仓；之前买了的最大利润今天卖获取更大利润
                profit_out: Math.max(profit[j].profit_out, profit[j].profit_in + prices[i]), 
                // 买入最大利润为昨天没有今天买，和昨天有
                profit_in: Math.max(profit[j].profit_in, profit[j-1].profit_out - prices[i])
            }
        }
    }
    return profit[k].profit_out
}

const maxProfit = function(prices) {

    /**
     * 这道题的难点就是冷冻期
     * 我们根据之前公式来推：
     * 卖出不变： dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i])
     * 买入必须在卖出后一天所以是 【i-2】： dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 2][k - 1][0] - prices[i])
     * 因为不限制买入次数所以k降纬
     */
    const n = prices.length;
    let price_in = -prices[0];
    let price_out = 0;
    let price_tmp = 0; // 存储前天

    for (let i = 1; i< n; i++) {
        const tmp = price_out; // 存下昨天;
        price_out = Math.max(price_out, price_in + prices[i]);
        
        price_in = Math.max(price_in, price_tmp - prices[i]);
        price_tmp = tmp; // 进入下次循环后 price_tmp 保存的其实是昨天的昨天，也就是前天
    }
}