leetcode 309. Best Time to Buy and Sell Stock with Cooldown 动态规划DP

墨蓝 2022-06-06 23:41 113阅读 0赞

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions:

You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).  
After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)  
Example:

prices = \[1, 2, 3, 0, 2\]  
maxProfit = 3  
transactions = \[buy, sell, cooldown, buy, sell\]

这道题和之前不一样的是，必须colddown一天

这道题是要求最多k次交易，建议和[leetcode 188. Best Time to Buy and Sell Stock IV 最大子段和][leetcode 188. Best Time to Buy and Sell Stock IV] 、[leetcode 123. Best Time to Buy and Sell Stock III 最大k次字段和 + DP][leetcode 123. Best Time to Buy and Sell Stock III _k_ _ DP] 、[leetcode 122. Best Time to Buy and Sell Stock II 最大子段和 + DP][leetcode 122. Best Time to Buy and Sell Stock II _ _ DP] 、[leetcode 121. Best Time to Buy and Sell Stock 最大字段和问题 + DP][leetcode 121. Best Time to Buy and Sell Stock _ _ DP] 一起学习。

注意本题和[leetcode 714. Best Time to Buy and Sell Stock with Transaction Fee 动态规划DP][leetcode 714. Best Time to Buy and Sell Stock with Transaction Fee _DP] 才是一样的做法，**之前的k次交易DP设置的是第i次交易之后sell和buy的最大利益，但是对于本题和714是不限制交易次数，那么DP设置的是第一天buy和sell之后的最大利益，所以这个虽然都是DP，但是做法是不一样的。**

嗯嗯，就是这么做的。

代码如下：

/*
     * http://blog.csdn.net/martinmateng/article/details/51104848
     *
     * 主要本题是有冰冻期的，是一个dp的题，设置两个数组buy[i]表示在第i天买了，
     * sell[i]表示在第i天卖了之后的最大利润。
     * dp[i]=max(dp[i-1],sell[i-2]-prices[i]) sell[i]=max(sell[i-1],buy[i-1]+prices[i]);
     * */
    public class Solution 
    {
            public int maxProfit(int[] prices) 
            {
                if(prices==null || prices.length<=0)
                    return 0;
    
                if(prices.length==0)
                    return 0;
                int[] sell=new int[prices.length];
                int[] buy=new int[prices.length];
                sell[0]=0;
                buy[0]=-prices[0];
    
                for(int i=1;i<prices.length;i++) 
                {
                    sell[i]=Math.max(sell[i-1], buy[i-1]+prices[i]);
                    if(i>=2) 
                        buy[i]=Math.max(buy[i-1], sell[i-2]-prices[i]);
                    else 
                        buy[i]=Math.max(buy[i-1], -prices[i]);
                }
                return sell[prices.length-1];
            }
        }

下面是C++的做法，就是一个简单的DP动态规划的做法，

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    
    using namespace std;
    
    class Solution
    {
    public:
        int maxProfit(vector<int>& p) 
        {
            if (p.size() <= 1)
                return 0;
    
            vector<int> sell = vector<int>(p.size(),0);
            vector<int> buy = vector<int>(p.size(),-p[0]);
            for (int i = 1; i < p.size(); i++)
            {
                sell[i] = max(sell[i - 1], p[i] + buy[i - 1]);
                if (i >= 2)
                    buy[i] = max(buy[i - 1], sell[i - 2] - p[i]);
                else
                    buy[i] = max(buy[i - 1],-p[i]);
            }
            return sell[p.size()-1];
        }
    };

[leetcode 188. Best Time to Buy and Sell Stock IV]: http://blog.csdn.net/jackzhang_123/article/details/78037522
[leetcode 123. Best Time to Buy and Sell Stock III _k_ _ DP]: http://blog.csdn.net/jackzhang_123/article/details/77988039
[leetcode 122. Best Time to Buy and Sell Stock II _ _ DP]: http://blog.csdn.net/jackzhang_123/article/details/77987707
[leetcode 121. Best Time to Buy and Sell Stock _ _ DP]: http://blog.csdn.net/jackzhang_123/article/details/77987643
[leetcode 714. Best Time to Buy and Sell Stock with Transaction Fee _DP]: http://blog.csdn.net/jackzhang_123/article/details/78884827