LeetCode 309 - Best Time to Buy and Sell Stock with Cooldown (Medium)

문제

LeetCode - 309번

풀이 과정

특정 날에 주식을 매도 혹은 매수하여 얻을 수 있는 최대 이윤을 계산하는 동적 계획법 문제입니다.

문제 조건에서 주식을 구매 전에는 판매를 먼저 해야한다는 것이 명시되어 있다는 점에 유의합니다.

만약 dp(i, buy) = i 번째 날 주식의 판매 상태가 buy 일 때 i 이후 얻을 수 있는 최대 이윤 이라고 정의한다면
다음과 같은 점화식을 얻을 수 있습니다.

dp(i, buy) = max(dp(i+1, true) - stock[i], dp(i+1, false)), if buy == false
else(buy == true), dp(i, buy) = max(dp(i+2, false) + stock[i], dp(i+1, true))

즉, `i` 번째 날 주식을 구매한 상태라면 해당 주식을 그날 판매하는 것과 판매하지 않고 다음 날로 넘어가는 경우를 비교해주고
반대로 구매하지 않은 상태라면 `i` 번째 날 구매하거나 구매하지 않고 넘어가는 것을 고려해서 최대 이윤을 구합니다.

코드

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (prices) {
  const memo = new Array(prices.length)
    .fill(0)
    .map((_) => new Array(2).fill(-1));

  function dp(i, buy) {
    if (i >= prices.length) return 0;

    if (memo[i][buy] !== -1) return memo[i][buy];

    if (!buy) memo[i][buy] = Math.max(dp(i + 1, 1) - prices[i], dp(i + 1, 0));
    else memo[i][buy] = Math.max(dp(i + 2, 0) + prices[i], dp(i + 1, 1));

    return memo[i][buy];
  }

  const answer = dp(0, 0);
  return answer;
};