Leetcode 309: 가장 좋 은 주식 매매 시 기 는 냉동기 (가장 상세 한 해법!!) 를 포함한다.

정수 배열 을 정 하 는데 그 중에서 i 번 째 요 소 는 i 일의 주식 가격 을 대표 합 니 다.
하나의 알고리즘 을 설계 하여 최대 이윤 을 계산 해 내다.다음 과 같은 제약 조건 을 만족 시 키 면 당신 은 가능 한 한 많은 거래 를 완성 할 수 있 습 니 다 (주식 을 여러 번 매매).

여러 거래 에 동시에 참여 할 수 없습니다.

주식 을 [를] 팔 면 다음 날 주식 을 살 수 없다 (즉, 냉동기 가 1 일).

예시:

  : [1,2,3,0,2]
  : 3 
  :         : [  ,   ,    ,   ,   ]

문제 풀이 의 사고 방향.
Leetcode 121: 주식 을 매매 하 는 가장 좋 은 시기 (가장 상세 한 해법!!)
Leetcode 122: 주식 매매 의 적기 II (가장 상세 한 해법!!)
Leetcode 123: 주식 매매 의 적기 III (가장 상세 한 해법!!)
이것 은 주식 시리즈 문제 중에서 현재 로 서 는 가장 어 려 운 것 이지 만 앞의 몇 가지 문제 의 사고 가 있어 서 이 문 제 는 해결 하기 가 매우 쉽다.먼저, 우 리 는 문제 에서 세 가지 상태 buy, sell 와 cooldown 를 언급 한 것 을 보 았 다. 그러면 우리 의 머 릿 속 의 첫 번 째 생각 은 바로 동태 계획 을 통 해 풀 어 내 는 것 이다.
만약 우리 index:i 일이 냉동기 라면 index:i-1 일 동안 주식 을 팔 았 다 는 것 만 설명 할 수 있 을 뿐이다. 그러면 i 일의 수익 은 i-1 일과 같다.

cooldown[i]=sell[i-1]

만약 우리 가 index:i 일 동안 판 매 를 고려 하여 이윤 을 가장 많이 요구한다 면.한 가지 상황 은 index:i-1 이날 주식 을 사 들 였 고, 다른 한 가지 상황 은 index:i-1 이전에 주식 을 보유 하고 index:i-1 일 에 도 팔 수 있다 는 것 이다. 그러면 우 리 는 index:i-1 매도 가 더 좋 은 지 고려 해 야 한다.아니면 index:i 더 잘 팔 리 나 요?

sell[i]=max(sell[i-1], buy[i-1]+prices[i])

만약 우리 가 index:i 일 동안 매입 을 고려 하여 이윤 을 가장 많이 요구한다 면.한 가지 상황 은 index:i-1 일이 냉동기 이 고, 다른 상황 은 index:i-1 일이 냉동기 가 아니 라 index:i-1 일 에 도 살 수 있다 는 것 이다. 그러면 우 리 는 index:i-1 매입 이 더 좋 은 지 고려 해 야 한다.아니면 index:i 사 는 게 나 을까요?

buy[i]=max(buy[i-1], cooldown[i-1]-prices[i])

우 리 는 첫날 에 팔 거나 동결 할 수 없다. 그러면 이 두 개 sell[0]=0 cooldown[0]=0 는 첫날 에 살 수 있 기 때문에 buy[0]=-prices[0].

class Solution:
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """  
        if not prices:
            return 0

        len_prices = len(prices)
        buy, sell, cooldown = [0]*len_prices, [0]*len_prices, [0]*len_prices
        buy[0] = -prices[0]
        for i in range(1, len_prices):
            cooldown[i] = sell[i-1]
            sell[i] = max(sell[i-1], buy[i-1] + prices[i])
            buy[i] = max(buy[i-1], cooldown[i-1] - prices[i])
        return sell[-1]

실제로 O(1) 의 공간 복잡 도 만 있 으 면 된다.

class Solution:
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """  
        if not prices:
            return 0

        len_prices = len(prices)
        buy, sell, cooldown = -prices[0], 0, 0
        for i in range(1, len_prices):
            pre_sell = sell
            sell = max(sell, buy + prices[i])
            buy = max(buy, cooldown - prices[i])
            cooldown = pre_sell
        return sell

물론 우리 도 재 귀 를 통 해 이 문 제 를 어떻게 풀 어야 할 지 생각해 봐 야 한다.우 리 는 새로운 방정식 _maxProfit(index, flag) 을 정의 합 니 다. index 은 어느 날 을 표시 하 는 지, flag 은 우리 가 그날 어떤 상태 (주식 을 보유 하 는 지, 보유 하지 않 는 지) 를 표시 합 니 다. 전체 함수 의 뜻 은 [index, len(prices)] 이 구간 에서 의 최대 수익 입 니 다.
우 리 는 index:i 일 째 주식 을 보유 하고 있다 면 당일 에 파 는 것 과 팔 지 않 는 것 중 어느 수익 이 높 은 지 를 고려 해 보 자.

max(_maxProfit(i+1, 'have'), _maxProfit(i+1, 'cooldown')) + prices[i] - prices[i-1]

우 리 는 index:i 일 째 주식 을 보유 하지 않 는 다 면 당일 에 어느 수익 이 높 은 지 를 고려 해 보 자.

max(_maxProfit(i+1, 'dhave'), _maxProfit(i+1, 'have'))

index:i 일이 동결 되면 우 리 는 index:i+1 일 동안 주식 을 보유 하지 않 을 것 이다.

_maxProfit(i+1, 'dhave')

저희 가 이 걸 통 해서 코드 를 빨리 쓸 수 있어 요.

class Solution:
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """  
        if not prices:
            return 0

        return self._maxProfit(prices, 0, 'dhave')
        
    def _maxProfit(self, prices, i, flag):
        if i == len(prices):
            return 0

        if flag == 'dhave':
            return max(self._maxProfit(prices, i + 1, 'dhave'), \
                        self._maxProfit(prices, i + 1, 'have'))
        elif flag == 'have':
            return max(self._maxProfit(prices, i + 1, 'have'), \
                        self._maxProfit(prices, i + 1, 'cooldown')) + prices[i] - prices[i-1]
        else:
            return self._maxProfit(prices, i + 1, 'dhave')

우 리 는 또한 기억 화 된 검색 방식 을 통 해 이 문 제 를 최적화 시 킬 수 있다.

class Solution:
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """  
        if not prices:
            return 0

        mem = dict()
        return self._maxProfit(prices, 0, 'dhave', mem)
        
    def _maxProfit(self, prices, i, flag, mem):
        if i == len(prices):
            return 0

        if (i, flag) in mem:
            return mem[(i, flag)]

        if flag == 'dhave':
            mem[(i, flag)] = max(self._maxProfit(prices, i + 1, 'dhave', mem), \
                        self._maxProfit(prices, i + 1, 'have', mem))
        elif flag == 'have':
            mem[(i, flag)] = max(self._maxProfit(prices, i + 1, 'have', mem), \
                        self._maxProfit(prices, i + 1, 'cooldown', mem)) + prices[i] - prices[i-1]
        else:
            mem[(i, flag)] = self._maxProfit(prices, i + 1, 'dhave', mem)
        
        return mem[(i, flag)]    

이로써 이 문 제 는 우리 에 의 해 완전히 해결 되 었 다.
나 는 이 문제 의 다른 언어 버 전 을 GitHub Leetcode 에 추가 했다.
문제 가 있 으 면 지적 해 주세요!!