188. Best Time to Buy and Sell Stock IV - Streak 1

내 풀이 접근

현재 인덱스까지 구할 수 있는 최대 수익을 계산하려면
이전 인덱스에 담겨 있는 최대 수익과, 그 인덱스부터 지금까지의 1회 최대 수익을 알고 있어야 한다.

이는 카데인 알고리즘과 굉장히 유사하다고 판단했다.

 

따라서 DP를 이용해 현재 인덱스까지 가장 최적의 이익을 찾도록 했다.

class Solution {

    public int maxProfit(int k, int[] prices) {
        int[][] dp = new int[prices.length + 1][k+1];
        int ret = 0;
        for(int kk = 1; kk<=k; kk++){
            for(int i = 1; i<=prices.length; i++){
                dp[i][kk] = dp[i-1][kk];
                for(int j = 0; j<i - 1; j++){
                    dp[i][kk] = Math.max(dp[i][kk], dp[j][kk-1] + prices[i-1] - prices[j]);
                    ret = Math.max(ret, dp[i][kk]);
                }
            }
        }
        return ret;
    }
}
// 1 3 2 4

/**
상태가 저장이 되어있어야 함
DP?
최솟값이 아니라, 이전 값 별로 갱신해야함
for()
    for()
        dp[i][k] = dp[j][k-1] + arr[]

*/

이래도 통과는 한다.
하지만, 조건이 빡빡하다면 통과하지 못했을 것이다.

좀 더 효율적인 해

이전에 구할 수 있는 최대 이익을, 0~i까지 전부 순회하지 말고 기억해둘 수는 없을까?

 

 

가격 별로 순회하는 부분을 자세히 보자.
결국 인덱스가 늘어나면, 바뀌는 경우의 수는 "지금 파는 행동" 뿐이다.
이후 dp 계산이 끝난뒤, "지금 사는 행동"이 가능해진다.

 

 

즉, 다음 두 시점을 분리할 수 있다.

• 지금 판매하는 행동
• 지금 구매하는 행동

이를 좀 더 형식적으로 정의하면, 다음과 같이 정의할 수 있다.

• 우리가 구하고자 하는 값: k번째 매도로 번 이익
• 우리가 최적을 위해 골라야 하는 것: 이전에 가장 저렴한 비용

판매를 먼저 해야 올바른 답을 구할 수 있다.
그 다음에 제일 효율적인 구매를 기록해두어야 한다.

 

 

기존 가격의 판매 시 최대 이익은 이전에 "가장 좋은 상태"에서 지금 팔아야 가능하다.
그럼 항상 "최고의 주식을 들고 있는 상태"를 가정할때, 다음과 같이 최적을 정의할 수 있다.

이는 초기조건 (dp[0][kk], dp[i][0])까지 잘 수렴한다.

 

 

그럼 이제 주식을 '항상 들고 있어야 하는 상태'를 가정해보자.
그러면 현재 얻은 주식은 다음과 같이 정리 가능하다.

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