動态規劃問題（十六）股票買賣問題

問題描述

給你一個數組

price[]

表示一支股票在第

天的價格為

price[i]

，現在有一些限制條件，要求在這些有限制的條件下求最大的股票收益。

限制條件為以下條件之一：

隻允許買賣一次 121. 買賣股票的最佳時機
可以無限制地買賣，在再次購買股票之前必須賣掉手中已有的股票 122. 買賣股票的最佳時機 II
最多買賣兩次股票，在再次購買之前必須賣掉手中已有的股票 123. 買賣股票的最佳時機 III
最多買賣 k 次股票，在再次購買之前必須賣掉手中已有的股票 188. 買賣股票的最佳時機 IV
可以無限制的買賣，含有冷凍期（在賣出股票之後的第二天不能再買入股票）309. 最佳買賣股票時機含冷凍期
可以無限制的買賣，買賣股票時包含手續費 714. 買賣股票的最佳時機含手續費

解決思路

參考：https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/discuss/108870/Most-consistent-ways-of-dealing-with-the-series-of-stock-problems

使用狀态機和動态規劃來解決這一類問題

對于目前的股票位置，對于買賣情況來講，隻有三種狀态：買入、賣出、不做任何處理。是以，這類問題的狀态機形式為：

對于目前的某個狀态，它能否進行下一步操作取決于兩個因素：目前的股票位置、可以進行買賣的次數。是以可以使用一個三維數組來建構一個狀态表：

fsm[i][k][s]

表示在第

天的位置，當可以進行買賣的次數為

時，目前股票持有狀态為

時能夠得到的最大收益。由于股票持有狀态隻能為持有或者沒有持有，是以

s=2

。

邊界情況：

當還沒有開始進行股票買賣時，即對第 0 天來講，當天沒有持有股票，目前的收益為 0。即 fsm[0][k][0] = 0
當還沒有開始進行股票買賣時，如果持有股票，這是不合理的，是以将它置為最小值。即 fsm[0][k][1] = Integer.MIN_VALUE
當可以買賣的股票次數為 0 時，那麼對于任意一天來講，能夠得到的收益都是 0。是以， fsm[i][0][0] = 0
當可以買賣的股票次數為 0，而如果此時持有股票的狀态是不可能出現的，是以也需要将它置為最小值。即 fsm[i][0][1] = Integer.MIN_VALUE

轉換方程：

對于任意的位置，目前沒有持有股票的狀态轉換方程如下所示：

\[T[i][k][0] = max(T[i - 1][k][0], T[i-1][k][1] + price[i])

\]

解釋：目前沒有持有股票隻能有兩種情況：一是之前手上沒有股票，今天也不買入這支股票；二是将之前手上持有的股票賣掉，是以需要加上持有的股票的價值。（注意問題描述中将的是一支股票的價格，是以目前股票的價值就是目前位置的股票價值）
在目前位置持有股票的狀态轉換方程如下：

\[T[i][k][1] = max(T[i - 1][k][1], T[i - 1][k - 1][0] - price[i])

解釋：目前位置持有股票隻能由兩種情況演變而來：一是之前手上持有股票，今天也不賣掉；二是之前手上沒有這支股票，現在買入，是以需要減去目前的股票價值。（由于買入會使用一次買票機會，是以這裡需要對
k 進行減一操作。當然，在賣出時在進行減一操作也是可以的。

對上文出現的情況進行解釋：

隻允許買賣一次
- 此時 k=1 ，執行上文的轉換方程即可
可以無限制地買賣，在再次購買股票之前必須賣掉手中已有的股票
- k=+Infinity ，按照無窮大的規則， k = k -1
  ，是以，上面的持有股票的轉換方程為：
  
  \[T[i][k][1] = max(T[i - 1][k][1], T[i - 1][k][0] - price[i])
最多買賣兩次股票，在再次購買之前必須賣掉手中已有的股票
- k=2
k 次股票，在再次購買之前必須賣掉手中已有的股票
- k 已經給出，直接執行上文的轉換方程即可
可以無限制的買賣，含有冷凍期（在賣出股票之後的第二天不能再買入股票）
- k 的情況與第二種情況一緻
- 此時的持有股票來源需要進行一下變換，由于存在一個冷凍期，是以需要從前前一日的狀态進行轉換，此時持有股票的轉換方程為：
  
  \[T[i][k][1] = max(T[i - 1][k][1], T[i - 2][k][0] - price[i])
可以無限制的買賣，買賣股票時包含手續費
- k
- 以上文的轉換方程實作即可，隻需要在每次買入時添加額外的手續費即可

實作

public class Solution {
    public int maxProfit(int[] prices) {
        final int N = prices.length;
        final int k = 1;
        int[][][] fsm = new int[N + 1][k + 1][2];

        fsm[0][k][0] = 0;
        fsm[0][k][1] = Integer.MIN_VALUE;

        for (int i = 1; i <= N; ++i) {
            fsm[i][0][0] = 0;
            fsm[i][0][1] = Integer.MIN_VALUE;
        }

        for (int i = 1; i <= N; ++i) {
            fsm[i][k][0] = Math.max(
                fsm[i - 1][k][0], 
                fsm[i - 1][k][1] + prices[i - 1]
            );

            fsm[i][k][1] = Math.max(
                fsm[i - 1][k][1], 
                fsm[i - 1][k - 1][0] - prices[i - 1]
            );
        }

        return fsm[N][k][0];
    }
}

進行空間壓縮：

public class Solution {
    public int maxProfit(int[] prices) {
        final int N = prices.length;

        int fsm_i_k_0 = 0, fsm_i_k_1 = Integer.MIN_VALUE;
        for (int price : prices) {
            fsm_i_k_0 = Math.max(fsm_i_k_0, fsm_i_k_1 + price);
            fsm_i_k_1 = Math.max(fsm_i_k_1, -price);
        }

        return fsm_i_k_0;
    }
}

public class Solution {
    public int maxProfit(int[] prices) {
        final int N = prices.length;
        final int k = 1;

        int[][][] fsm = new int[N + 1][k + 1][2];

        fsm[0][k][0] = 0;
        fsm[0][k][1] = Integer.MIN_VALUE;

        for (int i = 1; i <= N; ++i) {
            fsm[i][0][0] = 0;
            fsm[i][0][1] = Integer.MIN_VALUE;
        }

        for (int i = 1; i <= N; ++i) {
            fsm[i][k][0] = Math.max(
                fsm[i - 1][k][0],
                fsm[i - 1][k][1] + prices[i - 1]
            );

            fsm[i][k][1] = Math.max(
                fsm[i - 1][k][1],
                fsm[i - 1][k][0] - prices[i - 1]
            );
        }

        return fsm[N][k][0];
    }
}

public class Solution {
    public int maxProfit(int[] prices) {
        final int N = prices.length;

        int fsm_i_k_0 = 0, fsm_i_k_1 = Integer.MIN_VALUE;
        for (int i = 1; i <= N; ++i) {
            int tmp = fsm_i_k_0;

            fsm_i_k_0 = Math.max(fsm_i_k_0, fsm_i_k_1 + prices[i - 1]);
            fsm_i_k_1 = Math.max(fsm_i_k_1, tmp - prices[i - 1]);
        }

        return fsm_i_k_0;
    }
}

public class Solution {
    public int maxProfit(int[] prices) {
        final int N = prices.length;
        final int k = 2;
        
        int[][][] fsm = new int[N + 1][k + 1][2];

        fsm[0][1][0] = 0;
        fsm[0][1][1] = Integer.MIN_VALUE;
        fsm[0][2][0] = 0;
        fsm[0][2][1] = Integer.MIN_VALUE;

        for (int i = 1; i <= N; ++i) {
            fsm[i][0][0] = 0;
            fsm[i][0][1] = Integer.MIN_VALUE;
        }

        for (int i = 1; i <= N; ++i) {
            fsm[i][1][0] = Math.max(
                fsm[i - 1][1][0],
                fsm[i - 1][1][1] + prices[i - 1]
            );

            fsm[i][1][1] = Math.max(
                fsm[i - 1][1][1],
                fsm[i - 1][0][0] - prices[i - 1]
            );

            fsm[i][2][0] = Math.max(
                fsm[i - 1][2][0],
                fsm[i - 1][2][1] + prices[i - 1]
            );

            fsm[i][2][1] = Math.max(
                fsm[i - 1][2][1],
                fsm[i - 1][1][0] - prices[i - 1]
            );
        }

        return fsm[N][k][0];
    }
}

public class Solution {
    public int maxProfit(int[] prices) {
        final int N = prices.length;

        int fsm_i_10 = 0, fsm_i_11 = Integer.MIN_VALUE;
        int fsm_i_20 = 0, fsm_i_21 = Integer.MIN_VALUE;
        for (int i = 1; i <= N; ++i) {
            fsm_i_20 = Math.max(fsm_i_20, fsm_i_21 + prices[i - 1]);
            fsm_i_21 = Math.max(fsm_i_21, fsm_i_10 - prices[i - 1]);

            fsm_i_10 = Math.max(fsm_i_10, fsm_i_11 + prices[i - 1]);
            fsm_i_11 = Math.max(fsm_i_11, -prices[i - 1]);
        }

        return fsm_i_20;
    }
}

public class Solution {
    public int maxProfit(int k, int[] prices) {
        final int N = prices.length;

        int[][][] fsm = new int[N + 1][k + 1][2];
        
        for (int i = 1; i <= N; ++i) {
            fsm[i][0][0] = 0;
            fsm[i][0][1] = Integer.MIN_VALUE;
        }

        for (int i = 0; i <= k; ++i) {
            fsm[0][i][0] = 0;
            fsm[0][i][1] = Integer.MIN_VALUE;
        }

        for (int i = 1; i <= N; ++i) {
            for (int j = 1; j <= k; ++j) {
                fsm[i][j][0] = Math.max(
                    fsm[i - 1][j][0],
                    fsm[i - 1][j][1] + prices[i - 1]
                );

                fsm[i][j][1] = Math.max(
                    fsm[i - 1][j][1],
                    fsm[i - 1][j - 1][0] - prices[i - 1]
                );
            }
        }

        return fsm[N][k][0];
    }
}

含有冷凍期（在賣出股票之後的第二天不能再買入股票）

public class Solution {
    public int maxProfit(int[] prices) {
        final int N = prices.length;
        final int k = 2;

        int[][][] fsm = new int[N + 1][k + 1][2];
        fsm[0][k][0] = 0;
        fsm[0][k][1] = Integer.MIN_VALUE;

        for (int i = 1; i <= N; ++i) {
            fsm[i][k][0] = Math.max(
                fsm[i - 1][k][0],
                fsm[i - 1][k][1] + prices[i - 1]
            );

            if (i == 1) {
                fsm[i][k][1] = Math.max(
                    fsm[i - 1][k][1],
                    fsm[i - 1][k][0] - prices[i - 1]
                );

                continue;
            }

            fsm[i][k][1] = Math.max(
                fsm[i - 1][k][1],
                fsm[i - 2][k][0] - prices[i - 1]
            );
        }

        return fsm[N][k][0];
    }
}

public class Solution {
    public int maxProfit(int[] prices) {
        final int N = prices.length;

        int fsm_ik0 = 0, fsm_ik0_pre = 0;
        int fsm_ik1 = Integer.MIN_VALUE;

        for (int i = 1; i <= N; ++i) {
            int fsm_ik0_old = fsm_ik0;

            fsm_ik0 = Math.max(fsm_ik0, fsm_ik1 + prices[i - 1]);
            fsm_ik1 = Math.max(fsm_ik1, fsm_ik0_pre - prices[i - 1]);

            fsm_ik0_pre = fsm_ik0_old;
        }

        return fsm_ik0;
    }
}

public class Solution {
    public int maxProfit(int[] prices, int fee) {
        final int N = prices.length;
        final int k = 2;

        int[][][] fsm = new int[N + 1][k + 1][2];
        fsm[0][k][0] = 0;
        fsm[0][k][1] = Integer.MIN_VALUE;

        for (int i = 1; i <= N; ++i) {
            fsm[i][k][0] = Math.max(
                fsm[i - 1][k][0],
                fsm[i - 1][k][1] + prices[i - 1]
            );

            fsm[i][k][1] = Math.max(
                fsm[i - 1][k][1],
                fsm[i - 1][k][0] - prices[i - 1] - fee
            );
        }

        return fsm[N][k][0];
    }
}

public class Solution {
    public int maxProfit(int[] prices, int fee) {
        final int N = prices.length;

        int fsm_ik0 = 0, fsm_ik1 = Integer.MIN_VALUE;
        for (int i = 1; i <= N; ++i) {
            int fsm_ik0_old = fsm_ik0;
            fsm_ik0 = Math.max(fsm_ik0, fsm_ik1 + prices[i - 1]);
            fsm_ik1 = Math.max(fsm_ik1, fsm_ik0_old - prices[i - 1] - fee);
        }

        return fsm_ik0;
    }
}

動态規劃問題（十六）股票買賣問題

問題描述

解決思路

實作

繼續閱讀

HDU 5719 Arrange

746.使用最小花費爬樓梯 Min Cost Climing Stairs

[LeetCode]（面試題 17.21）直方圖的水量

LeetCode刷題系列——編輯距離

HDU 5119 Happy Matt Friends（01背包）

HDU 5119 Happy Matt Friends（dp） Happy Matt Friends

Codeforces Round #319 (Div. 2) B C D

HDU 4609 3-idiots

nyoj712 雙程動态規劃

NYOJ 269--VF

NYOJ - 252 - 01串(動态規劃)

一個小小的算法題

HDU 4717 The Moving Points

HDU 1402 A * B Problem Plus

數組和類數組

HDU 1160 FatMouse's Speed （記錄路徑的最長上升子序列）