算法

股票买卖问题

言七墨 · 9月6日 · 2020年 490次已读

葵花宝典

  • 状态转移框架
    • dp[i][k][1]:表示今天是第 i 天,手上持有股票,至今最多言七墨允许交易 k 次
    • dp[i][k][0]:表示今天是第 i 天,手上没有持有股票,至今最多允许交易 k 次
/**
 * 解释:今天我没有持有股票,有两种可能:
 *     1、要么是我昨天就没有持有,然后今天选择 rest,所以我今天还是没有持有;
 *     2、要么是我昨天持有股票,但是我今天 sell 了,所以我今天没有持有股票了。
 *            max(    选择 rest,           选择 sell           )
 */           
dp[i][k][0] = max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i])

/**
 * 解释:今天我持有着股票,有两种可能:
 *     1、要么我昨天就持有着股票,然后今天选择 rest,所以我今天还持有着股票;
 *     2、要么我昨天本没有持有,但今天我选择 buy,所以今天我就持有股票了。
 *            max(   选择 rest,             选择 buy               )
 */
dp[i][k][1] = max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i])
  • base case:
// 因为 i 是从 0 开始的,所以 i = -1 意味着还没有开始,这时候的利润为 0
dp[-1][k][0] = 0;

// 还没开始的时候,是不可能持有股票的,用负无穷表示这种情况不可能
dp[-1][k][1] = -infinity

// 因为 k 是从 1 开始,所以 k = 0 意味着不允许交易,这时候利润当然是 0
dp[i][0][0] = 0;

// 不允许交易的情况下,是不可能持有股票的,用负无穷表示这种情况不可能
dp[i][0][1] = -infinity
  • 归纳、总结:
// base case:
dp[-1][k][0] = dp[i][0][0] = 0;
dp[-1][k][1] = dp[i][0][1] = -infinity;
// 状态转移方程:
dp[i][k][0] = max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i]);
dp[i][k][1] = max(dp[i -1][k][1], dp[i - 1][k - 1][0] - prices[i]);

斩妖除魔

下面就通过上面的葵花宝典来斩杀以下 6 道题目:

  • 买卖七墨博客股票的最佳时机
  • 买卖股票的最佳时机 II
  • 买卖股票的最佳时机 III
  • 买卖股票的最佳时机 IV
  • 最佳买卖股票时机含冷冻期
  • 买卖股票的最佳时机含手续费

1、买卖股票的最佳时机

/**
 * >>>>>>>>>>>>>>>>>>>>>>>>>>>>>> 解法一:k == 1 <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
 * <p>
 *    由于本题要求的交易次数为1,故得到转移方程:
 *    dp[i][1][0] = max(dp[i - 1][1][0], dp[i - 1][1][1] + prices[i])
 *    dp[i][1][1] = max(dp[i - 1][1][1], dp[i - 1][0][0] - prices[i])  
 *    解释:已知当 k = 0 时,dp[i - 1][0][0] = 0。
 *            故 dp[i][1][1] = max(dp[i - 1][1][1], -prices[i])
 *
 *    现在发现 k 都是 1,不会改变,即 k 对状态转移已经没有影响了。
 *    可以进一步简化去掉所有 k,即
 *    dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i])
 *    dp[i][1] = max(dp[i - 1][1], -prices[i])
 *    base case:
 *        dp[0][0] = 0;
 *        dp[0][1] = -prices[i];
 */
public int maxProfit1(int[] prices) {
    int len = prices.length;
    if (len == 0) {
        return 0;
    }
    int[][] dp = new int[len][2];
    for (int i = 0; i < len; i++) {
        if (i - 1 == -1) {
            dp[i][0] = 0;
            dp[i][1] = -prices[i];
            continue;
        }
        dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
        dp[i][1] = Math.max(dp[i - 1][1], - prices[i]);
    }
    return dp[len - 1][0]; // 第二维参数:[1] 代表手上还持有股票,[0] 表示手上的股票已经卖出去了,很显然后者得到的利润一定大于前者
}

/**
 * >>>>>>>>>>>>>>>>>>>>>>>>>>>>>> 解法二:k == 1 <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
 * 状态压缩
 */
public int maxProfit2(int[] prices) {
    int len = prices.length;
    if (len == 0) {
        return 0;
    }
    // dp[-1][0] = 0, dp[-1][1] = -infinity
    int dp_i_0 = 0, dp_i_1 = Integer.MIN_VALUE;
    for (int i = 0; i < len; i++) {
        // dp[i][0] = max(dp[i - 1][0], dp[i][1] + prices[i])
        dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
        // dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i])
        dp_i_1 = Math.max(dp_i_1, -prices[i]);
    }
    return dp_i_0; // dp_i_1 代表手上还持有股票,dp_i_0 表示手上的股票已经卖出去了,很显然后者得到的利润一定大于前者
}

2、买卖股票的最佳时机 II

七墨博客
/**
 * >>>>>>>>>>>>>>>>>>>>>>>>>>>>>> k = +infinity <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
 * 如果 k 为正无穷,那么可以认为 k 和 k - 1 是一样的。可以这样改写框架:
 *      dp[i][k][0] = max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i])
 *      dp[i][k][1] = max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i])
 *                    = max(dp[i - 1][k][1], dp[i - 1][k][0] - prices[i])
 *      现在发现数组中的 k 已经不会改变了,也就是说不需要记录 k 这个状态了:
 *      dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i])
 *      dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i])
 */
public int maxProfit(int[] prices) {
    int len = prices.length;
    if (len == 0) {
        return 0;
    }
    // dp[-1][0] = 0, dp[-1][1] = -infinity
    int dp_i_0 = 0, dp_i_1 = Integer.MIN_VALUE;
    for (int i = 0; i < len; i++) {
        // dp_i_0 等价于状态转移方程中的 dp[i - 1][0]
        int temp = dp_i_0;
        // dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i])
        dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
        // dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i])
        dp_i_1 = Math.max(dp_i_1, temp - prices[i]);
    }
    return dp_i_0;
}

3、买卖股票的最佳时机 III

/**
     * >>>>>>>>>>>>>>>>>>>>>>>>>>>>>> k = 2 <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
     * k = 2 和前面题目的情况稍微不同,因为上面的情况都和 k 的关系不太大。要么 k 是正无穷,状态转移和 k 没关系了;要么 k = 1,跟 k = 0 这个 base case 挨得近,最后也没有存在感。
     * 这道题 k = 2 和后面要讲的 k 是任意正整数的情况中,对 k 的处理就凸显出来了
     * 状态转移方程:
     *     dp[i][k][0] = max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i]);
     *     dp[i][k][1] = max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i]);
     * base case:
     *     dp[0][k][0] = dp[i][k][0] = 0;
     *     dp[0][k][1] = dp[i][k][1] = -prices[0]; // 由状态转移方程可知,当 i = 0 时,dp[0][k][1] = max(dp[-1][k][1], dp[-1][k - 1][0] - prices[i]),
     *     而 dp[0 - 1][k -  1][0] = 0; 因为 i 是从 0 开始的,所以 i = -1 意味着还没有开始,这时候的利润为 0,故 dp[0][k][1] = -prices[0]
     */
    public int maxProfit(int[] prices) {
        int len = prices.length;
        if (len == 0) {
            return 0;
        }
        int maxK = 2;
        int dp[][][] = new int[len][maxK + 1][2];
        for (int i = 0; i < len; i++) {
            for (int k = maxK; k > 0; k--) { // 由于没有消掉 k 的影响,所以必须要对 k 进行穷举
                if (i - 1 == -1) {
                    dp[i][k][0] = 0;
                    dp[i][k][1] = -prices[i];
                    continue;
                }
                dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i]);
                dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i]);
            }
        }
        return dp[len - 1][maxK][0];
    }

4、买卖股票的最佳时机 IV

/**
 * >>>>>>>>>>>>>>>>>>>>>>>>>>>>>> k = any integer <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
 * 一次交易由买入和卖出构成,至少需要两天。所以说有效的限制 k 应该不超过 len/2,如果超过,就没有约束作用了,相当于 k = +infinity
 * 无约束:走`2、买卖股票的最佳时机 II`的逻辑
 * 有约束:
 * 状态转移方程:
 *     dp[i][k][0] = max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i]);
 *     dp[i][k][1] = max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i]); 
 * base case:
 *     dp[0][k][0] = dp[i][k][0] = 0;
 *     dp[0][k][1] = dp[i][k][1] = -prices[0]; // 由状态转移方程可知,当 i = 0 时,dp[0][k][1] = max(dp[-1][k][1], dp[-1][k - 1][0] - prices[i]),
 *     而 dp[0 - 1][k -  1][0] = 0; 因为 i 是从 0 开始的,所以 i = -1 意味着还没有开始,这时候的利润为 0,故 dp[0][k][1] = -prices[0]
 */
public int maxProfit(int k, int[] prices) {
    int len = prices.length;
    if (len == 0) {
        return 0;
    }
    if (k > len / 2) {
        return maxProfit(prices); // 调用`2、买卖股票的最佳时机 II`中的代码
    }
    int[][][] dp = new int[len][k + 1][2];
    for (int i = 0; i < len; i++) {
        for (int j = k; j > 0; j--) {
            if (i - 1 == -1) {
                dp[i][j][0] = 0;
                dp[i][j][1] = -prices[i];
                continue;
            }
            dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i]);
            dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i]);
        }
    }
    return dp[len - 1][k][0];
}

5、言七墨最佳买卖股票时机含冷冻言七墨

/**
 * >>>>>>>>>>>>>>>>>>>>>>>>>>>>>> k = +infinity with cooldown <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
 * base case:
 *     dp[-1][0] = 0;
 *     dp[-1][1] = -infinity;
 * 状态转移方程:
 *     dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i])
 *     dp[i][1] = max(dp[i - 1][1], dp[i - 2][0] - prices[i])
 * 解释:由于存在冷冻期,第 i 天选择 buy 的时候,要从 i-2 的状态转移,而不是 i-1 。
 */
public int maxProfit4(int[] prices) {
    int len = prices.length;
    if (len == 0) {
        return 0;
    }
    // dp[-1][0] = 0, dp[-1][1] = -infinity
    int dp_i_0 = 0, dp_i_1 = Integer.MIN_VALUE;
    // dp[i - 2][0] = 0
    int dp_pre_0 = 0; 
    for (int i = 0; i < len; i++) {
        int temp = dp_i_0;
        dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
        dp_i_1 = Math.max(dp_i_1, dp_pre_0 - prices[i]);
        dp_pre_0 = temp;
    }
    return dp_i_0; // dp_i_1 代表手上还持有股票,dp_i_0 表示手上的股票已经卖出去了,很显然后者得到的利润一定大于前者
}

6、买卖股票的最佳时机含手续费

/**
 * >>>>>>>>>>>>>>>>>>>>>>>>>>>>>> k = +infinity with fee <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
 * base case:
 *     dp[-1][0] = 0;
 *     dp[-1][1] = -infinity;
 * 每次交易要支付手续费,只要把手续费从利润中减去即可。改写方程:
 *      dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i])
 *      dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i] - fee)
 * 解释:相当于买入股票的价格升高了。
 * 在第一个式子里减也是一样的,相当于卖出股票的价格减小了。
 */
public int maxProfit(int[] prices, int fee) {
    int len = prices.length;
    if (len == 0) {
        return 0;
    }
    // dp[-1][0] = 0, dp[-1][1] = -infinity
    int dp_i_0 = 0, dp_i_1 = Integer.MIN_VALUE;
    for (int i = 0; i < len; i++) {
        int temp = dp_i_0;
        dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
        dp_i_1 = Math.max(dp_i_1, temp - prices[i] - fee);
    }
    return dp_i_0; // dp_i_1 代表手上还持有股票,dp_i_0 表示手上的股票已经卖出去了,很显然后者得到的利润一定大于前者
}

代码地址:Github

0 条回应