[LeetCode] 188. Best Time to Buy and Sell Stock IV

😎풀이

1. DP를 2중 배열로 초기화한다. (n은 각 일자, k는 거래 횟수 단, 0회 거래는 존재하지 않으므로 + 1 하여 초기화)
2. 첫째 날 고정 매수
3. 각 일자에 매수 및 매도 시 최댓값을 계산하여 dp를 채워나간다.

function maxProfit(k: number, prices: number[]): number {
    const n = prices.length
    // dp 초기화
    // n: 각 일자
    // k: 거래 횟수
    const dp = Array.from({length: n}, () => Array(k + 1).fill(0))
    for(let i = 1; i <= k; i++) {
        // 첫째 날 고정 매수
        let maxProfit = -prices[0]
        for(let j = 1; j < n; j++) {
            // dp[j - 1][i]: 오늘 매각하지 않음
            // maxProfit + prices[j]: 오늘 매각
            dp[j][i] = Math.max(dp[j - 1][i], maxProfit + prices[j])
            // maxProfit: 오늘 매수하지 않음
            // dp[j][i - 1] - prices[j]: 오늘 매수 
            maxProfit = Math.max(maxProfit, dp[j][i - 1] - prices[j])
        }
    }

    return dp[n - 1][k]
};