阅读 971

算法:买卖股票系列

Leetcode上有一个买卖股票系列的算法问题,主要区别在于是否有交易次数限制、是否交易有冷却期、是否有交易手续费等条件。本文探究的就是这个系列的通用思路和解法、不同条件时的修改以及最优解。阅读本文需要事先对这个系列各个问题的题目有一定的了解,了解动态规划。本文会从最复杂的条件开始,得出最通用的解法,所以一开始反而是最难的,推荐有兴趣、有耐心的读者先从头到尾阅读一遍,如果难以理解的话,再从最简单的条件开始阅读,这样就可以深刻了解这个系列的解题思路,掌握解题模板。本文代码使用的语言是Java

核心思路

定义一个二维数组int[][] profit = new int[n][2],其中profit[i][0]表示第i天卖出股票(没有持有股票)时的最大收益,profit[i][1]表示表示第i天买入股票(持有股票)时的最大收益

那么状态转移方程是:

// 第i天的卖出状态 = Max(前一天卖出状态,前一天买入状态 + 卖出股票获得的收益)
profit[i][0] = Math.max(profit[i - 1][0], profit[i - 1][1] + prices[i]);
// 第i天的买入状态 = Max(前一天买入状态,前一天前一次已卖出状态 - 买入股票扣除的收益)
profit[i][1] = Math.max(profit[i - 1][1], profit[i - 1][0] - prices[i]);
复制代码

这个系列所有问题的解答都是基于这个状态转移方程

最通用的解法

以下代码是包含了Leetcode上买卖股票系列所有不同条件下的通用解

// k表示交易次数,fee表示交易手续费,m表示交易冷却期
public int maxProfit(int k, int[] prices, int fee, int m) {
    if (k == 0 || prices == null || prices.length < 2) {
      	return 0;
    }
    int n = prices.length;
	
    // 进行一次完全的交易需要两天,所以当 k > n/2 的时候,就可以每天都进行一次买入(卖出)操作,也就是可以交易无数次
    if (k > (n >> 1)) {
      	int[][] profit = new int[n][2];
        for (int i = 0; i < n; i++) {
            // 处理初始状态
            if (i == 0) {
                profit[i][0] = 0;
                profit[i][1] = -prices[0];
                continue;
            }
            // 处理有交易冷却期时,前 m + 1 天的情况
            if (i < m + 1) {
                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], 0 - prices[i]);
                continue;
            }
            // 核心,状态转移方程
            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 - (m + 1)][0] - prices[i]);
            
        }
        return profit[n - 1][0];
    }
    
    int[][][] profit = new int[n][k + 1][2];

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < k + 1; j++) {
            // 处理初始状态
            if (i == 0) {
              	profit[i][j][0] = 0;
                profit[i][j][1] = -prices[0];
                continue;
            }
            if (j == 0) {
                profit[i][j][0] = 0;
                profit[i][j][1] = -prices[0];
              	continue;
            }
            // 处理有交易冷却期时,前 m + 1 天的情况
            if (i < m + 1) {
              	profit[i][j][0] = Math.max(profit[i - 1][j][0], profit[i - 1][j][1] + prices[i] - fee);
              	profit[i][j][1] = Math.max(profit[i - 1][j][1], 0 - prices[i]);
              	continue;
                
            }
            // 核心,状态转移方程
            profit[i][j][0] = Math.max(profit[i - 1][j][0], profit[i - 1][j][1] + prices[i] - fee);
            profit[i][j][1] = Math.max(profit[i - 1][j][1], profit[i - (m + 1)][j - 1][0] - prices[i]);
        }
    }
    return profit[n - 1][k][0];
}
复制代码

从上面函数可以看出,i表示的天数这一维度可以省略,但如果有交易冷却期这个条件的话,需要额外添加一个数组来保存[i - (m + 1), i - 1]天前的值,优化后的代码如下

public int maxProfit(int k, int[] prices, int fee, int m) {
    if (k == 0 || prices == null || prices.length < 2) {
        return 0;
    }
    
    int n = prices.length;

    if (k > (n >> 1)) {
        int sell = 0;
        int buy = Integer.MIN_VALUE + fee;
      	// 保存 [i - (m + 1), i - 1] 天前的值
        int[] preSells = new int[m + 1];
        for (int i = 0; i < prices.length; i++) {
            sell = Math.max(sell, buy + prices[i] - fee);
            buy = Math.max(buy, preSells[i % (m + 1)] - prices[i]);
            preSells[i % (m + 1)] = sell;
        }
        return sell;
    }
    
    int[] sells = new int[k];
    int[] buys = new int[k];
    // 保存 [i - (m + 1), i - 1] 天前的值
    int[][] preSells = new int[k][m + 1];
    
    // 处理初始状态
    for (int i = 0; i < k; i++) {
        sells[i] = 0;
        buys[i]=  Integer.MIN_VALUE + fee;
    }
	
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < k; j++) {
            if (j == 0) {
                sells[j] = Math.max(sells[j], buys[j] + prices[i] - fee);
                buys[j] = Math.max(buys[j], -prices[i]);
                preSells[j][i % (m + 1)] = sells[j];
                continue;
            }
            sells[j] = Math.max(sells[j], buys[j] + prices[i] - fee);
            buys[j] = Math.max(buys[j], preSells[j - 1][i % (m + 1)] - prices[i]);
            preSells[j][i % (m + 1)] = sells[j];
        }
    }
    return sells[k - 1];
}
复制代码

这个系列所有问题都可以在上面的代码基础上进行修改优化,去除不必要的代码即可得出解

只能交易k次

Leetcode的188题

由于只有一个交易次数的条件,所以不需要m,也不需要fee,直接简化代码即可

public int maxProfit(int k, int[] prices) {
    if (k == 0 || prices == null || prices.length < 2) {
     	 return 0;
    }
    
    int n = prices.length;

    // 进行一次完全的交易需要两天,所以当 k > n/2 的时候,就可以每天都进行一次买入(卖出)操作,也就是可以交易无数次
    if (k > (n >> 1)) {
        int[][] profit = new int[n][2];

        for (int i = 0; i < n; i++) {
            if (i == 0) {
                profit[i][0] = 0;
                profit[i][1] = -prices[0];
                continue;
            }
            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[n - 1][0];
    }

    int[][][] profit = new int[n][k + 1][2];

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < k + 1; j++) {
            if (i == 0) {
              	profit[i][j][0] = 0;
                profit[i][j][1] = -prices[0];
                continue;
            }
            if (j == 0) {
              	profit[i][j][0] = 0;
                profit[i][j][1] = -prices[0];
                continue;
            }
            profit[i][j][0] = Math.max(profit[i - 1][j][0], profit[i - 1][j][1] + prices[i]);
            profit[i][j][1] = Math.max(profit[i - 1][j][1], profit[i - 1][j - 1][0] - prices[i]);
        }
    }
    return profit[n - 1][k][0];
}
复制代码

优化

public int maxProfit(int k, int[] prices) {
    if (k == 0 || prices == null || prices.length < 2) {
        return 0;
    }

    int n = prices.length;

    if (k > (n >> 1)) {
        int sell = 0;
        int buy = Integer.MIN_VALUE;
        for (int price : prices) {
            sell = Math.max(sell, buy + price);
            buy = Math.max(buy, sell - price);
        }
        return sell;
    }

    int[] sells = new int[k];
    int[] buys = new int[k];

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

    for (int price : prices) {
        for (int i = 0; i < k; i++) {
            if (i == 0) {
                sells[i] = Math.max(sells[i], buys[i] + price);
                buys[i] = Math.max(buys[i], -price);
                continue;
            }
            sells[i] = Math.max(sells[i], buys[i] + price);
            buys[i] = Math.max(buys[i], sells[i - 1] - price);
        }
    }
    return sells[k - 1];
}
复制代码

只能交易两次

Leetcode的123题

由于只有一个交易次数的条件,所以不需要m,也不需要fee,直接简化代码得

public int maxProfit(int[] prices) {
    if (prices == null || prices.length < 2) {
      	return 0;
    }
    int k = 2;
    int n = prices.length;

    int[][][] profit = new int[n][k + 1][2];

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < k + 1; j++) {
            if (i == 0) {
                profit[i][j][0] = 0;
                profit[i][j][1] = -prices[0];
                continue;
            }
            if (j == 0) {
                profit[i][j][0] = 0;
                profit[i][j][1] = -prices[0];
                continue;
            }

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

    return profit[n - 1][k][0];
}
复制代码

优化,由于只能交易两次,所以只需要两组变量来保存结果即可

public int maxProfit(int[] prices) {
    int sell1 = 0;
    int buy1 = Integer.MIN_VALUE;
    int sell2 = 0;
    int buy2 = Integer.MIN_VALUE;

    for (int price : prices) {
        sell1 = Math.max(sell1, buy1 + price);
        buy1 = Math.max(buy1, -price);
        sell2 = Math.max(sell2, buy2 + price);
        buy2 = Math.max(buy2, sell1 - price);
    }
    return sell2;
}
复制代码

只能交易一次

Leetcode的121题

由于只有一个交易次数的条件,所以不需要m,也不需要fee;同时因为只能交易一次,所以k = 1,也就是可以省略

public int maxProfit(int[] prices) {
    if (prices == null || prices.length < 2) {
      	return 0;
    }
    int n = prices.length;
    int[][] profit = new int[n][2];

    for (int i = 0; i < n; i++) {
      	if (i == 0) {
      	    profit[i][0] = 0;
      	    profit[i][1] = -prices[0];
      	    continue;
      	}
      	profit[i][0] = Math.max(profit[i - 1][0], profit[i - 1][1] + prices[i]);
      	// 因为只能交易一次,所以这里的原来的 profit[i - 1][0] 恒等于 0
      	profit[i][1] = Math.max(profit[i - 1][1], -prices[i]);
    }
    return profit[n - 1][0];
}
复制代码

优化

public int maxProfit(int[] prices) {
    int sell = 0;
    int buy = Integer.MIN_VALUE;
    for (int price : prices) {
        sell = Math.max(sell, buy + price);
        buy = Math.max(buy, -price);
    }

    return sell;
}
复制代码

这个题目有更通俗直接的解法

// 遍历的同时,保存数组中的最小值,更新最大差值
public int maxProfit(int[] prices) {
    int profit = 0;
    int min = Integer.MAX_VALUE;
    for (int price : prices) {
        if (price < min) {
            min = price;
        } else if (price - min > profit) {
            profit = price - min;
        }
    }
    return profit;
}
复制代码

可以交易无数次

Leetcode的122题

由于只一个交易次数的条件,所以不需要m,也不需要fee;至于k这一维度,也可以删除,有两种理解方式

  1. 可以交易无数次,也就是k = +∞,这时候k ≈ k - 1,所以k可以认为是没有作用的,可以删除k这一维度
  2. 之前需要k这一维度是因为有交易次数限制,每天都要进行遍历,从k次交易内选择最优方案;但如果没有交易次数限制,则可以认为每天都进行交易,收益可以一直累加,下一天直接取之前的最优方案即可,所以可以删除k这一维度
public int maxProfit(int[] prices) {
    if (prices == null || prices.length < 2) {
      	return 0;
    }
    int n = prices.length;
    int[][] profit = new int[n][2];


    for (int i = 0; i < n; i++) {
        if (i == 0) {
            profit[i][0] = 0;
            profit[i][1] = -prices[0];
            continue;
        }
        profit[i][0] = Math.max(profit[i - 1][0], profit[i - 1][1] + prices[i]);
      	// 这里的 profit[i - 1][0] 表示前一天的最优方案,因为没有交易次数限制,也就是收益可以一直累加
        profit[i][1] = Math.max(profit[i - 1][1], profit[i - 1][0] - prices[i]);
    }
    return profit[n - 1][0];
}
复制代码

优化

public int maxProfit(int[] prices) {
    int sell = 0;
    int buy = Integer.MIN_VALUE;
    for (int price : prices) {
        sell = Math.max(sell, buy + price);
        buy = Math.max(buy, sell - price);
    }
    return sell;
}
复制代码

可以看出只能交易一次与可以交易无数次的区别:

  1. 只能交易一次,前一天的收益恒为0
  2. 可以交易无数次,收益可以一直累加

更通俗直接的解法,贪心

// 由于不限交易次数,所以只要后面的价格比较大,都能获得收益
public int maxProfit(int[] prices) {
    int maxProfit = 0;
    for (int i = 0; i < prices.length - 1; i++) {
        int today = prices[i];
        int tomorrow = prices[i + 1];
        if (today < tomorrow) {
            maxProfit += tomorrow - today; 
        }
    }
    return maxProfit;
}
复制代码

可以交易无数次,有一天的冷却期

Leetcode的309题

在可以交易无数次的条件上,加上m这个条件即可

public int maxProfit(int[] prices) {
    if (prices == null || prices.length < 2) {
        return 0;
    }
    // 如果冷却期是n天的话,让 m = n 即可
    int m = 1;
    int n = prices.length;
    int[][] profit = new int[n][2];


    for (int i = 0; i < n; i++) {
        if (i == 0) {
            profit[i][0] = 0;
            profit[i][1] = -prices[0];
            continue;
        }
        if (i < m + 1) {
            profit[i][0] = Math.max(profit[i - 1][0], profit[i - 1][1] + prices[i]);
            profit[i][1] = Math.max(profit[i - 1][1], 0 - prices[i]);
            continue;
        }
        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 - (m + 1)][0] - prices[i]);
    }
    return profit[n - 1][0];
}
复制代码

优化

public int maxProfit(int[] prices) {
    // 如果冷却期是n天的话,让 m = n 即可
    int m = 1;
    int sell = 0;
    int buy = Integer.MIN_VALUE;
    int[] preSells = new int[m + 1];
    for (int i = 0; i < prices.length; i++) {
        sell = Math.max(sell, buy + prices[i]);
        buy = Math.max(buy, preSells[i % (m + 1)] - prices[i]);
        preSells[i % (m + 1)] = sell;
    }
    return sell;
}
复制代码

可以交易无数次,无冷却期,有手续费

Leetcode的714题

在可以交易无数次的条件上,加上fee这个条件即可

public int maxProfit(int[] prices, int fee) {
    if (prices == null || prices.length < 2) {
      	return 0;
    }
    int n = prices.length;
    int[][] profit = new int [n][2];
    for (int i = 0; i < n; i++) {
        if (i == 0) {
            profit[i][0] = 0;
            profit[i][1] = -prices[0];
            continue;
        }
        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[n - 1][0];
}
复制代码

优化

public int maxProfit(int[] prices) {
    int sell = 0;
    // 以防溢出
    int buy = Integer.MIN_VALUE + fee;
    for (int price : prices) {
        sell = Math.max(sell, buy + price - fee);
        buy = Math.max(buy, sell - price);
    }
    return sell;
}
复制代码

总结

从最复杂的条件开始思考这个系列解法或许有点反人类,但是我个人觉得这样才是最能全局深刻理解掌握这个系列的办法,最复杂的情况都解决了,剩下的就很简单了。相信各位读者看完以上这么多不同条件下的解法以及优化后的代码,一定会对动态规划有更深的理解,如果有更优的解法,欢迎一起探讨。

关注下面的标签,发现更多相似文章
评论