LeetCode Day 동적 프로그래밍 9부

188. 주식을 사고 파는 가장 좋은 시기 IV

price[i]는 i번째 날 특정 주식의 가격이고 정수 k인 정수 배열 가격이 제공됩니다.

당신이 달성할 수 있는 최대 수익을 찾아보세요. 최대 k번의 거래를 완료할 수 있습니다. 즉, 최대 k번 구매하고 최대 k번 판매할 수 있습니다.

참고: 동시에 여러 거래에 참여할 수 없습니다(즉, 다시 구매하기 전에 주식을 판매해야 합니다).

예 1:

입력: k = 2, 가격 = [2,4,1]
출력: 2
설명: 1일차 매수(가격 = 2), 2일차 매도(가격 = 4), 이익 = 4-2 = 2.
예시 2:

입력: k = 2, 가격 = [3,2,6,5,0,3]
출력: 7
설명: 2일째 매수(가격 = 2), 3일째 매도(가격 = 6), 이익 = 6-2 = 4. 그런 다음 5일째 매수(가격 = 0), 6일째 매도(가격 = 3) , 이익 = 3-0 = 3.

제약사항:

1 1 0 <= 가격[i] <= 1000
원본페이지

    public int maxProfit(int k, int[] prices) {
        /**[0][0] do nothing in day 0
           [0][1] own the stock for 1st time in day 0
           [0][2] not own the stock for 1st time in day 0
           [0][3] own the stock for 2nd time in day 0
           [0][4] not own the stock for 2nd time in day 0
           ....
           [0][k*2-1] own the stock for kth time in day 0
           [0][k*2] not own the stock for kth time in day 0

           [1][1] = max([0][1],[0][0]-prices[1])
           [1][2] = max([0][2],[0][1]+prices[1])
           [1][3] = max([0][3],[0][2]-prices[1])

           [i][j] if j is odd means we need to pay for the stock or keep the own status
                  if j is even means we can sell the stock or keep the non-stock status

        */    
        int[][] dp = new int[prices.length+1][k*2+1];
        for(int i=1; i<=k*2; i+=2){
            dp[0][i] = -prices[0];
        }

        for(int i=1; i<prices.length; i++){
            for(int j=1; j<=k*2; j++){
                dp[i][j] = Math.max(
                    dp[i-1][j],
                    dp[i-1][j-1] + ((j % 2 == 0) ? 1 : -1) * prices[i]
                );
            }
        }
        return dp[prices.length-1][k*2];  
    }

309. 쿨다운으로 주식을 사고 팔기에 가장 좋은 시기

가격[i]이 i번째 날 특정 주식의 가격인 배열 가격이 제공됩니다.

당신이 달성할 수 있는 최대 수익을 찾아보세요. 다음 제한 사항에 따라 원하는 만큼 많은 거래를 완료할 수 있습니다(즉, 주식의 한 주를 여러 번 구매하고 판매).

주식을 매도한 후에는 다음 날(예: 하루 쿨타임)에 주식을 구매할 수 없습니다.
참고: 동시에 여러 거래에 참여할 수 없습니다(즉, 다시 구매하기 전에 주식을 판매해야 합니다).

예 1:

입력: 가격 = [1,2,3,0,2]
출력: 3
설명: 거래 = [구매, 판매, 쿨다운, 구매, 판매]
예시 2:

입력: 가격 = [1]
출력: 0

제약사항:

1 <= 가격.길이 <= 5000
0 <= 가격[i] <= 1000

    public int maxProfit(int[] prices) {

        /**
        [0] own the stock
        [1] colldown 
        [2] not own the stock 

         */

         int[][] dp = new int[prices.length][3];

         dp[0][0] = -prices[0];

         for(int i=1; i<prices.length; i++){
            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][2]-prices[i]);
            dp[i][1] = dp[i-1][0] + prices[i];
            dp[i][2] = Math.max(dp[i-1][1], dp[i-1][2]);
         }

        // Arrays.stream(dp).map(Arrays::toString).forEach(System.out::println);

         return Math.max(dp[prices.length-1][2],dp[prices.length-1][1]);

    }

쿨타임이 되면 새로운 주식을 살 수 없으니 주의하세요.

이 회귀 관계에서는 dp[2]가 쿨다운 조건을 계속 다룰 수 있도록 업데이트한 마지막 항목임을 보여줍니다.

714. 거래 수수료로 주식을 사고 팔기에 가장 좋은 시기

price[i]는 i번째 날 특정 주식의 가격이고 거래 수수료를 나타내는 정수 수수료인 배열 가격이 제공됩니다.

당신이 달성할 수 있는 최대 수익을 찾아보세요. 원하는 만큼 거래를 완료할 수 있지만 각 거래마다 거래 수수료를 지불해야 합니다.

참고:

동시에 여러 거래에 참여할 수 없습니다(즉, 다시 구매하기 전에 주식을 팔아야 합니다).
거래수수료는 주식 매입 및 매도 시 1회만 부과됩니다.

예 1:

입력: 가격 = [1,3,2,8,4,9], 수수료 = 2
출력: 8
설명: 최대 이익은 다음을 통해 달성할 수 있습니다.

• 가격으로 구매[0] = 1
• 가격에 판매[3] = 8
• 가격으로 구매[4] = 4
• 가격에 판매[5] = 9 총 이익은 ((8 - 1) - 2) + ((9 - 4) - 2) = 8입니다. 예시 2:

입력: 가격 = [1,3,7,5,10,3], 수수료 = 3
출력: 6

제약사항:

1 <= 가격.길이 <= 5 * 10^4
1 <= 가격[i] < 5 * 10^4
0 원본페이지

우리가 고려해야 할 유일한 것은 거래 수수료를 추가하는 것입니다. 그러나 수수료는 이전 논리를 바꾸지 않습니다

    public int maxProfit(int[] prices, int fee) {
        int[] dp = new int[2];
        int temp = 0;

        dp[0] = -prices[0];

        for(int i=1; i<prices.length; i++){
            temp = dp[1];
            dp[1] = Math.max(dp[1], dp[0] + prices[i] -fee);
            dp[0] = Math.max(dp[0], temp-prices[i]);

        }

        return dp[1]; 
    }

위 내용은 LeetCode Day 동적 프로그래밍 9부의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!