Leetcode 의 동적 기획 (DP) 주제 - 188. 주식 매매 의 적기 IV (Best Time to Buy and Sell Stock IV)

Leetcode 의 동적 기획 (DP) 주제 - 188. 주식 매매 의 적기 IV (Best Time to Buy and Sell Stock IV)
주식 문제:
121. 주식 매매 의 적기
122. 주식 매매 의 적기 II
123. 주식 매매 의 적기 III
188. 주식 매매 의 적기 IV
309. 가장 좋 은 주식 매매 시 기 는 냉동 기 를 포함한다.
714. 주식 을 매매 하 는 가장 좋 은 시 기 는 수수 료 를 포함한다.
 
배열 을 지정 합 니 다. i 하나의 요 소 는 주어진 주식 이 제 1 위 에 있다. i 하늘의 가격.
당신 이 얻 을 수 있 는 최대 이윤 을 계산 하기 위해 알고리즘 을 설계 하 세 요.너 는 기껏해야 완성 할 수 있다. k 거래
주의: 너 는 여러 건의 거래 에 동시에 참여 할 수 없다.
예시 1:

  : [2,4,1], k = 2
  : 2
  :    1   (     = 2)      ，   2   (     = 4)      ，           = 4-2 = 2 。

예시 2:

  : [3,2,6,5,0,3], k = 2
  : 7
  :    2   (     = 2)      ，   3   (     = 6)      ,            = 6-2 = 4 。
       ，   5   (     = 0)      ，   6   (     = 3)      ,            = 3-0 = 3 。

 
거래 횟수 를 제한 한 주식 문제.
DP 의미:
dp [i] [0] [k] 는 i 일 째 에 수중 에 주식 이 없어 거래 횟수 를 k 회의 최대 이윤 으로 제한 했다 고 밝 혔 다.
dp [i] [1] [k] 는 i 일 째 에 손 에 주식 이 있 고 거래 횟수 를 k 회의 최대 이윤 으로 제한 했다 고 밝 혔 다.
 
설명:

 、  i ，      ，     ：
　　1、 i-1       ， i    ，     
　　2、 i-1       ，   i      
 、  i ，     ，     ：
　　1、 i-1       ， i     
　　2、 i-1        ， i      

    ，  k>prices.length/2   ，k            。
       or   k   dp   。
      。

class Solution {
    public int maxProfit(int k, int[] prices) {
        if(prices==null || prices.length==0) return 0;
        if(k>prices.length/2){
            return maxProfit(prices);
        }
        int[][][] dp = new int[prices.length][2][k+1];
        for (int i = 0; i < k+1; i++) {
            dp[0][0][i] = 0;
            dp[0][1][i] = -prices[0];
        }
        for (int i = 1; i < prices.length; i++) {
            for (int k1 = 1; k1 <= k; k1++) {
                dp[i][0][k1] = Math.max(dp[i-1][0][k1],dp[i-1][1][k1]+prices[i]);
                dp[i][1][k1] = Math.max(dp[i-1][1][k1],dp[i-1][0][k1-1]-prices[i]);
            }
        }
        return dp[prices.length-1][0][k];
    }
    public int maxProfit(int[] prices) {
        if(prices==null || prices.length==0) return 0;
        int[][] dp = new int[prices.length][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for (int i = 1; i < prices.length; i++) {
            dp[i][0] = Math.max(dp[i-1][1]+prices[i],dp[i-1][0]);
            dp[i][1] = Math.max(dp[i-1][0]-prices[i],dp[i-1][1]);
        }
        return dp[prices.length-1][0];
    }
}