状态机求解最佳买卖股票时机

Posted on

很多读者抱怨股票系列问题奇技淫巧太多，如果面试真的遇到这类问题，基本不会想到那些巧妙的办法，怎么办？所以本文拒绝奇技淫巧，而是稳扎稳打，只用一种状态机方法解决所用问题，以不变应万变。

题解分析：

每天有三种状态：买入，卖出，保留。

dp[i][k][0]表示在第i天还剩k次交易机会，此时手中无股票。

dp[i][k][1]表示在第i天还剩k次交易机会，此时手中有股票。

状态转移方程：

  • 初始状态：

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])

买卖股票的最佳时机

题目地址

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/

题目描述

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。

注意你不能在买入股票前卖出股票。

主要代码

1
2
3
4
5
6
7
8
9
10
public int maxProfit(int[] prices) {
    int[][] profit = new int[prices.length][2];
    profit[0][0] = 0;
    profit[0][1] = -prices[0];
    for (int i = 1; i < prices.length; i++) {
        profit[i][0] = Math.max(profit[i - 1][0], profit[i - 1][1] + prices[i]);
        profit[i][1] = Math.max(profit[i-1][1],profit[i-1][0]-prices[i]);
    }
    return profit[prices.length-1][0];
}

买卖股票的最佳时机II

题目地址

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/

题目描述

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

主要代码

1
2
3
4
5
6
7
8
9
10
11
12
13
public int maxProfit(int[] prices) {
    int len = prices.length;
    if(len==0)
        return 0;
    int[][] profit = new int[len][2];
    profit[0][1] = -prices[0];
    profit[0][0] = 0;
    for (int i = 1; i < len; i++) {
        profit[i][0] = Math.max(profit[i - 1][0], profit[i - 1][1] + prices[i]);
        profit[i][1] = Math.max(profit[i - 1][1], profit[i - 1][0] - prices[i]);
    }
    return profit[len - 1][0];
}

买卖股票的最佳时机III

题目地址

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/

题目描述

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

主要代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int maxProfit(int[] prices) {
    int len = prices.length;
    if (len == 0)
        return 0;
    int[][][] profit = new int[len][3][2];
    profit[0][0][0] = 0;
    profit[0][1][0] = 0;
    profit[0][2][0] = 0;
    profit[0][0][1] = -prices[0];
    profit[0][1][1] = -prices[0];
    profit[0][2][1] = -prices[0];
    for (int i = 1; i < len; i++) {
        for (int k = 2; k >= 1; k--) {
            profit[i][k][0] = Math.max(profit[i - 1][k][0], profit[i - 1][k][1] + prices[i]);
            profit[i][k][1] = Math.max(profit[i - 1][k][1], profit[i - 1][k - 1][0] - prices[i]);
        }
    }
    return Math.max(Math.max(profit[len - 1][0][0], profit[len - 1][1][0]), profit[len - 1][2][0]);
}

买卖股票的最佳时机IV

题目地址

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/

题目描述

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。

注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

主要代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int len = prices.length;
if (len == 0)
    return 0;
int[][][] profit = new int[len][k + 1][2];
for (int t = 0; t <= k; t++) {
    profit[0][t][0] = 0;
    profit[0][t][1] = -prices[0];
}
for (int i = 1; i < len; i++) {
    for (int t = k; t >= 1; t--) {
        profit[i][t][0] = Math.max(profit[i - 1][t][0], profit[i - 1][t][1] + prices[i]);
        profit[i][t][1] = Math.max(profit[i - 1][t][1], profit[i - 1][t - 1][0] - prices[i]);

    }
}
int res = 0;
for (int t = 0; t <= k; t++) {
    res = Math.max(res, profit[len - 1][t][0]);
}
return res;

最佳买卖股票时机含冷冻期

题目地址

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/

题目描述

给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。​

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

* 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
* 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

主要代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int maxProfit(int[] prices) {
    int len = prices.length;
    if (len == 0)
        return 0;
    int[][] profit = new int[len][2];
    profit[0][0] = 0;
    profit[0][1] = -prices[0];
    for (int i = 1; i < len; i++) {
        profit[i][0] = Math.max(profit[i - 1][0], profit[i - 1][1] + prices[i]);
        if (i >= 2) {
            profit[i][1] = Math.max(profit[i - 1][1], profit[i - 2][0] - prices[i]);
        } else {
            profit[i][1] = Math.max(-prices[1], -prices[0]);
        }
    }
    return profit[len - 1][0];
}

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

题目地址

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/

题目描述

给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格 ；非负整数 fee 代表了交易股票的手续费用。

你可以无限次地完成交易，但是你每次交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。

返回获得利润的最大值。

主要代码

1
2
3
4
5
6
7
8
9
10
11
12
13
public int maxProfit(int[] prices, int fee) {
    int len = prices.length;
    if (len == 0)
        return 0;
    int[][] profit = new int[len][2];
    profit[0][0] = 0;
    profit[0][1] = -prices[0];
    for (int i = 1; i < len; i++) {
        profit[i][0] = Math.max(profit[i - 1][0], profit[i - 1][1] + prices[i]-fee);
        profit[i][1] = Math.max(profit[i - 1][1], profit[i - 1][0] - prices[i]);
    }
    return profit[len - 1][0];
}