DP数组应该保存什么？

  • 题目要求的是根据价格数组买卖股票的最大收益，但是DP数组不能简单的设置成在第i天卖出股票能获得的最大收益（这样类似于贪心的做法，无法依赖于前面的状态）。
  • DP数组应该设置为当天持股dp[i][1]或不持股dp[i][0]所能获得的最大收益，这样当天持股或不持股的收益依赖于前一天持股或不持股的收益，最后一天不持股的收益即为当前能获得的最大收益。

最小子问题

  • 第一天不持股，收益为0：dp[0][0] = 0
  • 第一天持股，即买入当天股票，收益为负的该股票价格：dp[0][1] = -prices[0]

如何思考状态转移方程？

  • 如果当天不持股，则当天的收益依赖于前一天是否持股的收益最大值，即比较下面两种情况的最大值：
  • 如果前一天不持股，说明当天不持股是因为前面几天都没买入股票，则当天的收益最大值跟前一天不持股的收益最大值一样：dp[i][0] = dp[i-1][0]
  • 如果前一天持股，说明当天不持股是将前面买入的股票在今天卖掉，则当天收益的最大值为前面持股的收益（买入股票的负收益）加上今天卖出股票的收益：dp[i][0] = dp[i-1][1] + prices[i]
  • 如果当天持股，则当天的收益依赖于前一天是否持股的收益最大值，即比较下面两种情况的最大值：
  • 如果前一天持股，说明当天持股是前面买入的股票，则当天的收益最大值跟前一天持股的收益最大值一样：dp[i][1] = dp[i-1][1]
  • 如果前一天不持股，说明当天持股是前面几天都没买股票（前面几天收益都为0，如果股票可以买卖多次，则前面几天的收益的收益为dp[i-1][0]），今天买股票持股，此时收益为：dp[i][1] = -prices[i]
/**
  * 
  * @param prices int整型一维数组 
  * @return int整型
  */
function maxProfit( prices ) {
    // write code here
    const dp = Array.from(new Array(prices.length), () => new Array(2).fill(0));  // dp数组保存当天持股或者不持股可以获得的最大收益
    dp[0][0] = 0;  // 第一天不持股，收益为0
    dp[0][1] = -prices[0];  // 第一天持股，即买入当天股票，收益为负的该股票的价格

    for (let i = 1; i < prices.length; ++i) {
        // 当天持股或不持股的收益依赖于前一天持股或不持股的收益
        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];
}
module.exports = {
    maxProfit : maxProfit
};