## Leetcode: the best time to buy and sell stocks, including handling charges (Python)

A good function 2020-11-13 02:56:59

## 1. Title Description

Given an array of integers prices, Among them the first i Elements represent the i Day's share price ; Non-negative integer fee Represents the handling fee for trading shares .

You can close the deal indefinitely , But you have to pay a commission for every transaction . If you have bought a stock , You can't buy any more stock until you sell it .

Return the maximum profit .

Example 1:

Input : prices = [1, 3, 2, 8, 4, 9], fee = 2
Output : 8
explain : The maximum profit that can be achieved :
Sell... Here prices = 8
Sell... Here prices = 9
Total profit : ((8 - 1) - 2) + ((9 - 4) - 2) = 8.

Be careful :

0 < prices.length <= 50000.
0 < prices[i] < 50000.
0 <= fee < 50000.

## 2. Ideas

The general idea is similar to the second question in the stock question series ： The best time to buy and sell stocks ||
Because there is a service charge , So let's assume that when we buy stocks , You need to pay for it . So the transformation equation between States , Change is needed ： As there is no limit to the number of shares to be traded , So there's no need to think about k and k-1 The problem of .

### 2.1 Code

``````class Solution:
def maxProfit(self, prices: List[int], fee: int) -> int:
if len(prices) == 0:
return 0
n = len(prices)
dp_i_0 = 0
dp_i_1 = -prices-fee
for i in range(1,n):
dp_i_0 = max(dp_i_0,dp_i_1+prices[i])
dp_i_1 = max(dp_i_1,dp_i_0-prices[i]-fee)
return dp_i_0
``````