LeetCode 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/

걸린 시간

- 실패

시간초과 풀이

C++

class Solution {
public:
    int n;
    vector<int> cache;
    int dp(int bi, int& fee, vector<int>& prices){
        // 기저 사례
        if(bi == n) return 0;
        // 메모이제이션
        int& ret = cache[bi];
        if(ret != -1) return ret;
        // 재귀 호출
        ret = 0;
        ret = max(ret, dp(bi+1, fee, prices)); // not buy
        for(int si = bi+1; si < n; si++) // buy and sell
            ret = max(ret, dp(si+1, fee, prices)+((prices[si]-prices[bi])-fee));
        return ret;
    }
    int maxProfit(vector<int>& prices, int fee) {
        n = prices.size();
        cache.resize(n, -1);
        return dp(0, fee, prices);
    }
};

34번째 테스트케이스에서 시간초과를 받았다.

구매와 판매를 한번에 처리하는 바람에 캐시 배열은 하나만 이용해도 됬지만, 구매한 상태에서 팔지 않고 다음날로 넘어가는 상태가 중복되게 된다.

풀이

C++

class Solution {
public:
    int n;
    vector<vector<int>> cache;
    int dp(int idx, int bought, int& fee, vector<int>& prices){
        // 기저 사례
        if(idx == n) return 0;
        // 메모이제이션
        int& ret = cache[idx][bought];
        if(ret != -1) return ret;
        // 재귀 호출
        ret = 0;
        if(bought) ret = max(ret, dp(idx+1, 0, fee, prices)+prices[idx]);
        else ret = max(ret, dp(idx+1, 1, fee, prices)-prices[idx]-fee);         
        ret = max(ret, dp(idx+1, bought, fee, prices)); // not buy
        return ret;
    }
    int maxProfit(vector<int>& prices, int fee) {
        n = prices.size();
        cache.resize(n, vector<int>(2, -1));
        return dp(0, 0, fee, prices);
    }
};

상태를 나누어 2차원 cache 배열의 형태로 메모이제이션 하면 각 단계별로 3개만의 재귀 호출이 일어나게 된다.

top-down dp 의 설계도 아직 많이 서툰데 bottom-up 풀이를 보니 갈길이 너무 멀어 보인다...