“This is the 19th day of my participation in the First Challenge 2022. For details: First Challenge 2022”
The title
Given an array of integers prices, the ith element represents the stock price on the ith day; The non-negative integer fee represents the processing cost of trading shares.
You can complete transactions as many times as you want, but you have to pay a fee for each transaction. If you have already bought a stock, you cannot continue to buy it until you have sold it.
Returns the maximum profit earned.
Note: a transaction refers to the entire process of buying, holding and selling a stock, and you only have to pay a fee for each transaction.
Example 1: Input: prices = [1, 3, 2, 8, 4, 9], fee = 2 Output: 8
Prices [3] = 8 Prices [4] = 4 Prices [5] = 9 Total profit: (8-1) -2) + (9-4) -2) = 8.
Note:
- 0 < prices.length <= 50000.
- 0 < prices[i] < 50000.
- 0 <= fee < 50000.
Their thinking
- Determine the meaning of the DP array and subscripts
Dp [I][j], when the state is J on day I, the maximum remaining cash is DP [I][j].
- State 1 dp[I][0] The maximum amount of money held in the stock state on day I
- In state TWO, dp[I][1] is the maximum amount of capital held in the non-shareholding state on day I
- Determine the recursion formula
Max (dp[i-1][0],dp[i-1][1] -prices [I] -fee); Max (dp[i-1][0],dp[i-1][1] -prices [I] -fee);
Dp [I][1] = math. Max (dp[i-1][1],dp[i-1][0] + prices[I]);
- How is a DP array initialized
Dp [0][0] = -prices[0] -fee I don’t own the stock state, state two, I initialize it to zero,
- Determine the traversal order
It can be seen from the recursive formula that DP [I] depends on DP [i-1], so it is traversed from front to back.
var maxProfit = function(prices, fee) {
let len = prices.length;
let dp = Array.from(Array(len),() = >Array(2).fill(0));
dp[0] = [-prices[0] - fee, 0];
for (let i = 1; i < len; i++) {
dp[i][0] = Math.max(dp[i - 1] [0],dp[i - 1] [1] - prices[i] -fee);
dp[i][1] = Math.max(dp[i - 1] [1],dp[i - 1] [0] + prices[i]);
}
return dp[len - 1] [1];
};
Copy the code