题解 | #股票（一次交易）#

• dp数组及其下标的含义：

  • dp数组的含义：记录手中的现金收益
  • 数组下标含义：
    • dp[i][0]：第i天结束，没有股票时的现金收益；
    • dp[i][1]：第i天结束，持有股票的现金收益；

• 递推公式

  • 第i天结束没有股票时的现金
    • 第i-1天没有股票时的现金 + 第i天休息，没有收益——即dp[i - 1][0]
    • 第i-1天持有股票时的现金+ 第i天卖出的收益——即dp[i - 1][1] + prices[i]
  • 第i天结束持有股票时的收益
    • 第i-1天没有股票的现金 + 第i天买入股票，现金流出——即：dp[i - 1][0] - prices[i] = -prices[i]（因为只有一次购买机会，所以此时的买入必是首次买入，则dp[i - 1][0] = 0）;
    • 第i-1天持有股票的现金 + 第i天休息，没有收益——即dp[i - 1][1] + 0

• 数组初始化

  • 第一天不持有股票，收益为0；
  • 第一天买入股票，则收益为-prices[0]

• 遍历顺序

  • 后一天的收益仅与前一天有关。自前向后一维遍历

public class Solution {
    public int maxProfit (int[] prices) {
        if(prices == null || prices.length == 0){
            return 0;
        }

        //1.创建dp数组
        int[][] dp = new int[prices.length][2];

        //2. 初始化
        dp[0][0] = 0;
        dp[0][1] = -prices[0];

        //3.遍历顺序
        for(int i = 1; i < prices.length; i++){
            //4. 递推公式，保证两种状态下各自收益最大
            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[prices.length - 1][0];
    }
}