买股票问题

121. 买卖股票的最佳时机

你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        //dp数组，dp[i][j],今天是第i天，交易状态为j，利润为dp[i][j];
        int[][] dp =new int[n][2];
        for(int i =0;i<n;i++){
            //base case
            if(i==0){
                dp[i][0] =0;
                dp[i][1] = -prices[i];
                continue;
            }
            //0代表已卖出，手中无股票；1代表未卖出，手中持有股票
            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[n-1][0];
    }
}

122. 买卖股票的最佳时机 II

输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
     随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。
     总利润为 4 + 3 = 7 。

class Solution {
    //特殊之处：可以进行无数次买卖，所以在进行一次买入时可能总利润已经为正数
    //而只能进行一次买卖的情况下，在买入前的总利润只能为零
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[][] dp = new int[n][2];
        for(int i=0;i<n;i++){
            if(i==0){
                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],dp[i-1][0]-prices[i]);
        }
        return dp[n-1][0];
    }
}

123. 买卖股票的最佳时机 III

最多进行两笔交易
输入：prices = [3,3,5,0,0,3,1,4]
输出：6
解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
     随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。

class Solution {
    //因为限制了买卖次数，所以需要一个三维的dp数组来进行穷举和状态转移
    //k代表到第i天内，可以最多进行k次交易
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int max_k = 2;
        int[][][] dp = new int[n][max_k+1][2];
        for(int i=0;i<n;i++){
            for(int k=max_k;k>0;k--){
                if(i==0){
                    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]);
                //在买入的时候进行k的状态转移，因为一次买入就代表一次交易的开始
                dp[i][k][1] = Math.max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]);
            }
        }
        return dp[n-1][max_k][0];
    }
}

188. 买卖股票的最佳时机 IV

自定义k的情况
输入：k = 2, prices = [2,4,1]
输出：2
解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。

class Solution {
    //需要对k进行判断，若k大于某个值便按照无限次来计算，避免了超时的情况
    public int maxProfit(int k, int[] prices) {
        int n =prices.length;
        if(n==0) return 0;
        if(k>n/2) return ifKequalsInfinite(prices);
        int[][][] dp = new int[n][k+1][2];
        for(int i=0;i<n;i++){
            //当k=0时，取一些永远不可能的特殊值
            dp[i][0][0] = 0;
            dp[i][0][1] = -666;
        }
        for(int i=0;i<n;i++){
            for(int j=k;j>0;j--){
                if(i==0){
                    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]);
                //如果要保证今天可以进行一次交易，那么到昨天的总交易次数最大只能为j-1，留下一次给今天
                dp[i][j][1] = Math.max(dp[i-1][j][1],dp[i-1][j-1][0]-prices[i]);
            }
        }
        return dp[n-1][k][0];
    }
    //当k足够大时，看作无限大
    int ifKequalsInfinite(int[] prices){
         int n = prices.length;
        int[][] dp = new int[n][2];
        for (int i = 0; i < n; i++) {
            if (i - 1 == -1) {
            // base case
            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], dp[i-1][0] - prices[i]);
    }
    return dp[n - 1][0];
    }
}