[LeetCode] 714. Best Time to Buy and Sell Stock with Transaction Fee, Medium

1. 문제

• 날짜 별 주식 가격 prices가 주어지고, 판매 수수료 fee가 주어질 때 최대 수익을 반환하라.
• 단, 주식은 하나 들고 있으면 팔기 전 까지 추가로 매수할 수 없다.

2. 해결

function maxProfit(prices: number[], fee: number): number {
    const n = prices.length;
    const dp: number[][] = Array.from({ length: n }, () => [0, 0]);

    dp[0][0] = 0;           // 0일차: 주식 없음 → 수익 0
    dp[0][1] = -prices[0];  // 0일차: 주식 삼 → 마이너스 수익

    for (let i = 1; i < n; i++) {
        // 오늘 주식 안 가진 상태: (1) 계속 안 가짐, (2) 오늘 판다
        dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee);

        // 오늘 주식 가진 상태: (1) 계속 가짐, (2) 오늘 삼
        dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
    }

    return dp[n - 1][0]; // 마지막 날은 주식 없이 끝나는 게 수익 최대
}

• 일단 풀 지 못했다. 경우의 수를 생각하지 못했다. 여기서는 각 날짜 별 가질 수 있는 상태는 주식을 가지고 있거나, 가지고 있지 않는 것.
• 0은 가지고 있지 않고, 1은 가지고 있는 상태라고 했을 때, 
  • dp[i][0]은 주식을 가지고 있지 않아야 하므로, 전 날 그대로 가지고 있지 않거나 전날에 산 주식을 판매한 가격 중 최대 값을 가진다.
  • dp[i][1]은 주식을 가지고 있어야 하므로, 전 날 산 주식을 그대로 가지거나 어제 안 산 현금을 기반으로 주식을 사는 가격 중 최대값을 가진다.