Best Time to Buy and Sell Stock with Transaction Fee

새로운 DP 문제를 풀었다. 확실히 저번 문제에서 오랜 시간동안 이해하려고 노력했고 원리를 이해하다보니 이번에는 답을 보지 않고 노트에 적으면서 문제를 잘 풀 수 있었다. 이번 문제는 저번 Cooldown 문제보다 조금은 더 쉽다고 느껴졌다, 왜냐하면은 특별한 조건 없이 Sell 을 할때 Fee만 나오는것이기 때문이다.

결국 이 문제에서도 계속 생각해야 했던 부분은 어떤 부분이 제일 겹쳤고 어떤 부분을 변수로 잡아서 계속 따라가다 보면은 한번의 For룹으로 끝낼 수 있었다. 전에 있었던 Cooldown 문제는 누적된 가장 큰 Profit은 DP[i-2] 였지만 이번 문제에서 누적되는 가장 큰 Profit은 DP[i-1] 이다. 왜냐하면은 현재 값에서 팔게 되었을때 가장 큰 Profit이 나올 수도 있기때문이다.

이런 로직을 따라가다 보면은 이 문제를 쉽게 풀 수 있고, 좀 이해 안가더라고 계속해서 파는게 좋을거같다.

class Solution {
    public int maxProfit(int[] prices, int fee) {
        if(prices.length == 1) return 0; 
        int[] dp = new int[prices.length]; 
        dp[0] = 0; 
        int max_price = -prices[0]; 
        for(int i = 1; i < prices.length; i++){
            dp[i] = Math.max(dp[i-1],max_price + prices[i] - fee); 
            max_price = Math.max(max_price,dp[i] - prices[i]); 
        }

        return dp[prices.length-1]; 
    }
}