[leetcode][309] Best Time to Buy and Sell Stock with Cooldown

문제 : https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/

---

주식가격이 주어질 때 최대 이익을 구하라.

동시에 여러개의 교환은 진행될 수 없다. (즉, 주식을 샀으면 팔때까지 다른 주식을 사고팔수없다.)

주식을 팔았을 때 다음날엔 어떠한 거래도 할 수 없다. (쿨다운 1일)

---

오랜만에 dfs + dp(memoization).

top-down 방식으로 풀었다.

dfs(index)를 stock[index~]을 사고 팔 때 얻을 수 있는 최대이익을 가져오는 함수라하자.

이 값은 index에서 어떠한 거래도 하지 않았을 때(dfs(index+1))와 index를 샀을때로 나뉠 수 있다.

index 번째 주식을 구입했으면 팔아야 한다.

index+1 이상의 인덱스 j에서 index 주식을 팔았을 때 얻을 수 있는 이익(prices[j] - prices[index])과 dfs(j+2)(쿨다운 1일 이므로 다음날은 뛰어넘어야 해서 +2)의 합들 중 최대 값이 dfs(index) 값이 된다.

dfs[index] = max(dfs[index+1], // 거래하지 않았을 때
              max(prices[j] - prices[index] + dfs[j+2]))(let, j > index) // 거래하는 경우

이를 점화식으로 정리하면 위와 같다.

dfs(마지막 주식 인덱스)가 정답이 된다.

 

시간복잡도는 O(N^2)

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/309.%20Best%20Time%20to%20Buy%20and%20Sell%20Stock%20with%20Cooldown.cpp