[LeetCode] 123. Best Time to Buy and Sell Stock III

😎풀이

dp를 통해 다양한 상탯값을 설정하고, 초기화를 진행하여 문제를 풀이하였음

function maxProfit(prices: number[]): number {
    const n = prices.length;
    
    // 각 날짜별로 가능한 모든 상태를 저장할 3차원 배열 생성
    // dp[i][k][state]
    // i: 현재 날짜
    // k: 남은 거래 횟수 (2번까지 가능)
    // state: 0=주식을 보유하지 않은 상태, 1=주식을 보유한 상태
    const dp: number[][][] = Array(n)
        .fill(0)
        .map(() => 
            Array(3)
                .fill(0)
                .map(() => Array(2).fill(0))  // 초기 소지금
        );
    
    // 초기 상태 설정
    // 첫째 날의 상태 초기화
    for (let k = 0; k <= 2; k++) {
        // 주식을 보유하지 않은 상태는 0으로 시작
        dp[0][k][0] = 0;
        // 주식을 보유한 상태는 첫날 가격을 지불한 상태
        dp[0][k][1] = -prices[0];
    }
    
    // 모든 날짜에 대해 반복
    for (let i = 1; i < n; i++) {
        for (let k = 0; k <= 2; k++) {
            // 주식을 보유하지 않은 상태
            if (k < 2) {
                // 이전 상태에서 최대값 선택
                dp[i][k][0] = Math.max(
                    dp[i-1][k][0],              // 이전에도 보유하지 않은 상태 유지
                    dp[i-1][k+1][1] + prices[i] // 이전에 보유한 주식을 판매
                );
            } else {
                dp[i][k][0] = dp[i-1][k][0];    // k=2일때는 거래불가, 이전 상태 유지
            }
            
            // 주식을 보유한 상태
            if (k > 0) {
                // 이전 상태에서 최대값 선택
                dp[i][k][1] = Math.max(
                    dp[i-1][k][1],              // 이전의 보유 상태 유지
                    dp[i-1][k][0] - prices[i]   // 새로 주식 구매
                );
            }
        }
    }
    
    // 마지막 날에 가능한 모든 상태 중 최대 이익 반환
    // 주식을 보유하지 않은 상태만 고려 (모든 거래가 완료된 상태)
    return Math.max(
        dp[n-1][0][0], // 2번의 거래가 모두 완료된 상태
        dp[n-1][1][0], // 1번의 거래만 완료된 상태
        dp[n-1][2][0]  // 거래를 하지 않은 상태
    );
}