Best Time to Buy and Sell Stock IV

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/description/

풀기 전

Naive하게 풀면 복잡도가 상당히 높아질 것으로 예상된다. Exponential로 예상
N^2까지 줄여줘야한다.
⇒ 전형적인 DP문제다.
점화식을 세운다.
- f(i, k)는 [0, i]구간에서 k번의 거래로 얻을 수 있는 최대수익을 의미한다.
- f(i, 0)은 항상 0이다. (거래가 없으면 돈을 얻을 수 없으므로)
- f(0, k)도 항상 0이다. (구간 [0, 0]에는 요소가 하나밖에 없으므로 거래에 필요한 최소 개수 2개보다 적어 거래를 할수가 없다.)
- f(i, k)는 다음 두 가지 중에 더 큰 값이다.
  - i에서 판매하는 경우
    - j’에서 구입했다고 가정
    - 판매수익 + 판매하기 이전에 얻은 수익
    - 판매수익 = prices[i] - prices[j’]
    - 판매 이전에 얻은 수익 = f(j’, k-1)
    - j’의 범위는 0 ~ i - 1
    - 즉 prices[i] - prices[j’] + f(j’, k-1) 의 최대값
    - 정리하면 prices[i] + max( f(j’, k-1) - prices[j’] )
  - i에서 판매하지 않는 경우
    - i 이전까지 k번 거래해서 얻은 수익
    - f(i - 1, k)

코드 설명

점화식을 그대로 코드로 옮기기만 하면 된다.

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        dp = [[0] * (k + 1) for _ in range(len(prices))] # N x (k + 1) array

        for kk in range(1, k + 1):
            maxCost = -prices[0] # initial value of dp[i, kk - 1] - prices[i] # i = 0
            for i in range(len(prices)):
                dp[i][kk] = max(dp[i - 1][kk], prices[i] + maxCost)
                maxCost = max(maxCost, dp[i][kk - 1] - prices[i])
        
        return dp[len(prices) - 1][k]

복잡도 분석

시간복잡도는 O(kn)

공간복잡도도 똑같다.