leetcode medium : Best time to buy and sell stock 2

다시 풀어도 어려운 DP문제!

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

LeetCode - The World's Leading Online Programming Learning Platform

 

그리디 하게 풀면 간단하게 풀리지만 DP적인 접근을 해보는 것도 좋다.

각 단계에서 아무것도 안하거나 사거나 팔거나, 이 세 가지 중 하나를 할 수 있는데

 

dp variable을 두 개로 나눠서 푼다.

1. 마지막으로 한 행동이 주식을 산거일때 i에서의 최대수익 (꼭 i에서 샀을 필요는 없다. i-2나 i-5에서 샀어도 됨. 마지막으로 한 행동이 산거이기만 하면 됨)

2. 마지막으로 한 행동이 주식을 판거일때 i에서의 최대수익

 

미자믹으로 한 행동이 주식을 산거일때 i에서 최대수익은 둘중하나다

(1) 이전에 주식을 사고 i에선 가만히 있거나

(2) 이전에 주식을 팔았었고 i에서 사거나

 

마지막으로 한 행동이 주식을 판거일때 i에서 최대수익은 둘중하나다.

(1) 이전에 주식을 팔았고 i에서 가만히 있거나

(2) 이전에 주식을 샀었고 i에서 팔거나

 

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        lastBuy, lastSell = -prices[0], 0
        curBuy, curSell = lastBuy, lastSell

        # buy[i] = 마지막으로 주식을 샀을때 i에서 최대수익
        # sell[i] = 마지막으로 주식을 팔았을때 i에서 최대수익
        # buy[i] = max (아무것도 안했을 때, i에서 샀을 때)
        #       = max (buy[i-1], sell[i-1] - price[i])
        # sell[i] = max (아무것도 안했을 때, i에서 팔았을 때)
        #       = max (sell[i-1], buy[i-1] + price[i])

        for i in range(1, len(prices)):
            curBuy = max(lastBuy, lastSell - prices[i])
            curSell = max(lastSell, lastBuy + prices[i])
            lastBuy, lastSell = curBuy, curSell
        
        return curSell

최대수익은 마지막으로 한 행동이 판 행동일때 나오므로 curSell을 반환하면 된다.

 

아래 솔루션이 문제를 dp로 보는데에 많은 도움이 됨

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/solutions/278953/another-view-to-the-problem-in-a-dp-way/

LeetCode - The World's Leading Online Programming Learning Platform