• 題目描述 （原題目鏈接）

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]

• 解題思路 （原思路鏈接）

這道題目自己一開始根本沒有想到用動態規劃，菜鳥本色。之后看了dicussion區域排名第一的答案，也是云里霧里。
還好碰到了這個解決思路。這個方案把每天分為四個狀態

有股票，賣 = 前天（有股票，休息）+ price 或者 前天（沒股票，買）+ price

有股票，休息 = 前天（有股票，休息）或者 前天（沒股票，買）

沒股票，買 = 前天（沒股票，休息）- price ==》 冷卻期所以不可能是 有股票，賣

沒股票，休息 = 前天（沒股票，休息）或者 前天（有股票，賣）

結合這個思路，編碼實現如下：

需要額外注意的一點是第0天的初始化，（有股票，休息）= -price 因為下一天可能賣這個股票，所以計價時相當于第0天買了。

int maxProfit(vector<int>& prices) {int has_sell, has_sell_before;int has_rest, has_rest_before;int no_buy, no_buy_before;int no_rest, no_rest_before;int size = prices.size();if(size < 2)return 0;has_sell_before = 0;has_rest_before = -prices[0];no_buy_before = -prices[0];no_rest_before = 0;for(int i = 1; i < size; i++){has_sell = max(has_rest_before + prices[i], no_buy_before + prices[i]);has_rest = max(has_rest_before, no_buy_before);no_buy = no_rest_before - prices[i];no_rest = max(no_rest_before, has_sell_before);has_sell_before = has_sell;has_rest_before = has_rest;no_buy_before = no_buy;no_rest_before = no_rest;}// find the max between has_sell and no_restreturn max(has_sell, no_rest);}

?

轉載于:https://www.cnblogs.com/niuxu18/p/note_leetcode_1.html

總結

以上是生活随笔為你收集整理的leetcode笔记（一）309. Best Time to Buy and Sell Stock with Cooldown的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。