1+ M
2+ 1531728802
3+ tags : Array , DP , Greedy , Sequence DP , Status DP
4+ time : O (n )
5+ space : O (n ), O (1 ) rolling array
6+
7+ 跟Stock II 一样 , 买卖无限 , 需先买在卖 . 附加条件 : 每个sell transaction要加一笔fee .
8+
9+ #### Sequence DP
10+ - 与StockII一样 , dp [i ]: represents 前i天的最大profit .
11+ - sell 的时候 , 才完成了一次transaction , 需要扣fee ; 而买入不扣fee .
12+ - model sell on dp [i ] day (which depends on dp [i -1 ]) and each day can be sell /buy => add status to dp [i ][status ]
13+ - status [0 ] buy on this day , status [1 ] sell on this day
14+ - dp [i ][0 ] = Math .max (dp [i -1 ][0 ], dp [i - 1 ][0 ] - prices [i ]);
15+ - dp [i ][1 ] = Math .max (dp [i -1 ][1 ], dp [i - 1 ][1 ] + prices [i ] - fee );
16+ - init : dp [0 ][0 ,1 ] = 0 ; dp [1 ][1 ] = 0 ; dp [1 ][0 ] = - prices ;
17+ - return dp [n ][1 ]
18+
19+ ```
20+ /*
21+ Your are given an array of integers prices,
22+ for which the i-th element is the price of a given stock on day i;
23+ and a non-negative integer fee representing a transaction fee.
24+
25+ You may complete as many transactions as you like,
26+ but you need to pay the transaction fee for each transaction.
27+ You may not buy more than 1 share of a stock at a time (ie. you must sell the stock share before you buy again.)
28+
29+ Return the maximum profit you can make.
30+
31+ Example 1:
32+ Input: prices = [1, 3, 2, 8, 4, 9], fee = 2
33+ Output: 8
34+ Explanation: The maximum profit can be achieved by:
35+ Buying at prices[0] = 1
36+ Selling at prices[3] = 8
37+ Buying at prices[4] = 4
38+ Selling at prices[5] = 9
39+ The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8.
40+ Note:
41+
42+ 0 < prices.length <= 50000.
43+ 0 < prices[i] < 50000.
44+ 0 <= fee < 50000.
45+ */
46+
47+ /*
48+ - sequence dp. dp[i] represents max profit for first i days.
49+ - model sell on dp[i] day (which depends on dp[i-1]) and each day can be sell/buy => add status to dp[i][status]
50+ - status[0] buy on this day, status[1] sell on this day
51+ - dp[i][0] = Math.max(dp[i-1][0], dp[i - 1][0] - prices[i]);
52+ - dp[i][1] = Math.max(dp[i-1][1], dp[i - 1][1] + prices[i] - fee);
53+ - init: dp[0][0,1] = 0; dp[1][1] = 0; dp[1][0] = - prices;
54+ return dp[n][1]
55+ */
56+ class Solution {
57+ public int maxProfit (int [] prices , int fee ) {
58+ if (prices == null || prices .length <= 1 ) return 0 ;
59+ // init dp[][] with n+1
60+ int n = prices .length ;
61+ int [][] dp = new int [n + 1 ][2 ];
62+ dp [0 ][0 ] = dp [0 ][1 ] = 0 ;
63+ dp [1 ][1 ] = 0 ;
64+ dp [1 ][0 ] = - prices [0 ];
65+
66+ // calculate dp
67+ for (int i = 2 ; i <= n ; i ++) {
68+ dp [i ][0 ] = Math .max (dp [i -1 ][0 ], dp [i - 1 ][1 ] - prices [i - 1 ]);
69+ dp [i ][1 ] = Math .max (dp [i -1 ][1 ], dp [i - 1 ][0 ] + prices [i - 1 ] - fee );
70+ }
71+
72+ return dp [n ][1 ];
73+ }
74+ }
75+
76+ // Rolling array
77+ class Solution {
78+ public int maxProfit (int [] prices , int fee ) {
79+ if (prices == null || prices .length <= 1 ) return 0 ;
80+ // init dp[][] with n+1
81+ int n = prices .length ;
82+ int [][] dp = new int [2 ][2 ];
83+ dp [0 ][0 ] = dp [0 ][1 ] = 0 ;
84+ dp [1 ][1 ] = 0 ;
85+ dp [1 ][0 ] = - prices [0 ];
86+
87+ // calculate dp
88+ for (int i = 2 ; i <= n ; i ++) {
89+ dp [i %2 ][0 ] = Math .max (dp [(i - 1 )%2 ][0 ], dp [(i - 1 )%2 ][1 ] - prices [i - 1 ]);
90+ dp [i %2 ][1 ] = Math .max (dp [(i - 1 )%2 ][1 ], dp [(i - 1 )%2 ][0 ] + prices [i - 1 ] - fee );
91+ }
92+
93+ return dp [n %2 ][1 ];
94+ }
95+ }
96+ ```
0 commit comments