714. Best Time to Buy and Sell Stock with Transaction Fee

714. Best Time to Buy and Sell Stock with Transaction Fee

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/

문제

풀이(처음 풀었던 코드 - TLE발생)

위에 코드 로직은 다음과 같다. Example 1으로 예를 들자면
prices = [1, 3, 2, 8, 4, 9]에서 for문을 통해 1보다 큰 값을 찾는다. 3을 찾았을 때 이익(3 - 1 - 2)을 계산하고 재귀구조로 [2, 8, 4, 9]를 위에 방법대로 찾는다. 하지만 원하는 것은 최대값이므로 모든 경우의 수에서 최대값을 찾고 DP라는 캐시에 저장한다.

아무래도 재귀구조 안에 2중 포문이라 시간복잡도가 상당히 클 걸로 예상했고, 통과하지 못했다.
이러한 알고리즘을 풀기 위해선 어떻게 해야하는지 찾아보았다.

풀이(DP)

주식을 가지고 있을 때, 주식을 가지고 있지 않을 때를 자기고 그래프를 그릴 수 가 있다.

결과