leetcode 714

题目

例子

思路1

使用dp[n][2] 存储最佳利润值，动态规划的思路，重要的是转移方程。

代码1

class Solution {
public:
int maxProfit(vector& prices, int fee) {
int n = prices.size();
//dp[i][0] 前i天手里没有股票的最大利润
//dp[i][1] 前i天手里有股票的最大利润
vector<vector> dp(n, vector(2));
dp[0][1] -= prices[0];

    /*
    [1,3,2,8,4,9]
    dp[0][0] = 0
    dp[0][1] = -1

    dp[1][1] = -1
    dp[1][0] = 0

    dp[2][1] = -1 
    dp[2][0] = 0
    0-2 天都不适合交易股票，最大利润是0
    */ 

    for(int i=1; i<n; i++){

        dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i]-fee);
        dp[i][1] = max(dp[i-1][0]-prices[i], dp[i-1][1]);
    }

    return dp[n-1][0];
}

};

思路2

使用贪心算法

代码2

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int n = prices.size();
        int buy = prices[0] + fee;
        int profit =0;

        /*
        case1:
        [1,3,7,5,10,3], fee=3
        profit 10-1 -3 = 6

        case2:
        [1,3,7,3,10,3], fee=3
        7-1-3 + (10-2-3) = 7    
        */
        for(int i=1;i<n; i++){
            if(prices[i]+fee < buy){
                // 买贵了
                buy = prices[i] + fee;
            }else if(prices[i] > buy){
                cout<< "buy : "<< buy << endl;
                cout<< "prices:" << prices[i] << endl;
                // 价格涨了，可以买股票了
                profit += (prices[i] - buy);
                // buy 设置为当前值，于之后比较看是否存在prices[i]+fee < buy, 存在证明多段profit 和是最优解
                buy = prices[i];
            }
        }

        return profit;

    }
};