動(dòng)態(tài)規(guī)劃

使用場(chǎng)景：重復(fù)子問(wèn)題

步驟：

1、定義公式

2、初始化變量

3、寫(xiě)循環(huán)體

? ? ?給定一個(gè)數(shù)組 prices ，它的第?i 個(gè)元素?prices[i] 表示一支給定股票第 i 天的價(jià)格。

?? ? 你只能選擇 某一天 買(mǎi)入這只股票，并選擇在 未來(lái)的某一個(gè)不同的日子 賣(mài)出該股票。設(shè)計(jì)一個(gè)算法來(lái)計(jì)算你所能獲取的最大利潤(rùn)。

?? ? 返回你可以從這筆交易中獲取的最大利潤(rùn)。如果你不能獲取任何利潤(rùn)，返回 0 。

?? ? 輸入：[7,1,5,3,6,4]

?? ? 輸出：5

?? ? 解釋?zhuān)涸诘?2 天（股票價(jià)格 = 1）的時(shí)候買(mǎi)入，在第 5 天（股票價(jià)格 = 6）的時(shí)候賣(mài)出，最大利潤(rùn) = 6-1 = 5 。

? ? ? ? ? 注意利潤(rùn)不能是 7-1 = 6, 因?yàn)橘u(mài)出價(jià)格需要大于買(mǎi)入價(jià)格；同時(shí)，你不能在買(mǎi)入前賣(mài)出股票。

? ? func?stock(?_prices : [Int]) ?-> Int {

? ? ? ? let?size = prices.count

? ? ? ? var?dp: [[Int]] = [[Int]](repeating: [Int](repeating:0, count:2), count: size)

? ? ? ? /*

?? ? ? ? step1:推導(dǎo)公式

?? ? ? ? 定義一個(gè)二維數(shù)組，用來(lái)存放當(dāng)天股票的狀態(tài)

?? ? ? ? 0表示當(dāng)天持有股票

?? ? ? ? 1表示當(dāng)天不持有股票

?? ? ? ? 持有股票的狀態(tài)有兩種情況；1，前一天就持有，保持狀態(tài) 2，前一天不持有，當(dāng)天買(mǎi)入

?? ? ? ? 不持有股票的狀態(tài)有兩種情況；1，前一天不持有，保持狀態(tài) 2，前一天持有，當(dāng)天賣(mài)出

?? ? ? ? dp[i][0] = max(dp[i-1][0],dp[i-1][i]-prices[i])

?? ? ? ? dp[i][1] = max(dp[i-1][1], -prices[i])

?? ? ? ? step2:初始化

?? ? ? ? 第一天持有股票，買(mǎi)入就需要花費(fèi)，所以：dp[0][0] = -prices[0]

?? ? ? ? 第一天不持有股票，第一天不能賣(mài)出，所以：dp[0][1] = 0

?? ? ? ? step3:寫(xiě)循環(huán)體

?? ? ? ? */

? ? ? ? dp[0][0] =-prices[0]

? ? ? ? dp[0][1] =0

? ? ? ? for?i?in?1 ..< size {

? ? ? ? ? ? dp[i][0] =max(dp[i-1][0],-prices[i])

? ? ? ? ? ? dp[i][1] =max(dp[i-1][1], dp[i-1][0]+prices[i])

? ? ? ? }

? ? ? ? return?dp[size-1][1]

? ? }

????買(mǎi)賣(mài)股票的最佳時(shí)機(jī)2

?? ? https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/

?? ? 給定一個(gè)數(shù)組，它的第?i 個(gè)元素是一支給定股票第 i 天的價(jià)格。

?? ? 設(shè)計(jì)一個(gè)算法來(lái)計(jì)算你所能獲取的最大利潤(rùn)。你可以盡可能地完成更多的交易（多次買(mǎi)賣(mài)一支股票）。

?? ? 注意：你不能同時(shí)參與多筆交易（你必須在再次購(gòu)買(mǎi)前出售掉之前的股票）。

func?stock2(_prices:[Int]) ->Int{

? ? ? ? /*

? ? step1: 推導(dǎo)公式

? ? ? ? //dp[i][0] 表示第i天持有股票，所得現(xiàn)金

? ? ? ? /*

?? ? ? ? 1、前一天就持有股票，所得現(xiàn)金為前一天持有股票的所得現(xiàn)金 dp[i-1][0]

?? ? ? ? 2、前一天不持有股票，所得現(xiàn)金為前一天持有股票+今天股票的價(jià)格dp[i-1][1]+prices[i]

?? ? ? ? */

? ? ? ? //dp[i][1] 表示第i天不持有股票，所得現(xiàn)金

? ? ? ? /*

?? ? ? ? 1、前一天就持有股票，所得現(xiàn)金為前一天不持有股票的所得現(xiàn)金減今天的股票價(jià)格 dp[i-1][1]-prices[i]

?? ? ? ? 2、前一天不持有股票，所得現(xiàn)金為

? ? ? ? ? ? 前一天不持有股票，那么保持現(xiàn)狀dp[i-1][1]

? ? ? ? ? ? 前一天持有股票，今天賣(mài)出，即：dp[i-1][0]+prices[i]

?? ? ? ? */

? ? ? ? let?size = prices.count

? ? ? ? var?dp:[[Int]] = [[Int]](repeating: [Int](repeating:0, count:2), count: size)

? ? ? ? /*

? ? ? ? step2:初始化

????????*/

? ? ? ? dp[0][0] =-prices[0]

? ? ? ? dp[0][1] =0

? ? ? ? /*

? ? ? ? step3:寫(xiě)循環(huán)體

????????*/

? ? ? ? for?index?in?1 ..< size {

? ? ? ? ? ? dp[index][0] =max(dp[index-1][1]-prices[index], dp[index-1][0])

? ? ? ? ? ? dp[index][1] =max(dp[index-1][1], dp[index-1][0]+prices[index])

? ? ? ? }

? ? ? ? return?dp[size-1][1]

? ? }

? ? ?題目鏈接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/

?? ? 給定一個(gè)整數(shù)數(shù)組 prices ，它的第 i 個(gè)元素 prices[i]是一支給定的股票在第 i 天的價(jià)格。

?? ? 設(shè)計(jì)一個(gè)算法來(lái)計(jì)算你所能獲取的最大利潤(rùn)。你最多可以完成 k 筆交易。

?? ? 注意：你不能同時(shí)參與多筆交易（你必須在再次購(gòu)買(mǎi)前出售掉之前的股票）。

?? ? 示例 ：

?? ? 輸入：k = 2, prices =[3,2,6,5,0,3]

?? ? 輸出：7

?? ? 解釋?zhuān)涸诘?2 天 (股票價(jià)格 = 2) 的時(shí)候買(mǎi)入，在第 3 天 (股票價(jià)格 = 6) 的時(shí)候賣(mài)出, 這筆交易所能獲得利潤(rùn) = 6-2 = 4。隨后，在第 5 天 (股票價(jià)格 = 0) 的時(shí)候買(mǎi)入，在第 6 天 (股票價(jià)格 = 3) 的時(shí)候賣(mài)出, 這筆交易所能獲得利潤(rùn) = 3-0 = 3 。

func?stock4(?_?prices: [Int],?_k :Int) -> Int {

? ? ? ? /*

?? ? ? ? 因?yàn)樵O(shè)計(jì)到最多次數(shù)k，所以定義一個(gè)二維數(shù)組，使用j表示當(dāng)天的狀態(tài)

?? ? ? ? 比如：k=2，那么就最多有兩次買(mǎi)入、兩次賣(mài)出 還有可能不操作，所以用

?? ? ? ? 0表示不操作 1買(mǎi)入 2賣(mài)出 3買(mǎi)入 4賣(mài)出，那么當(dāng)天的狀態(tài)就有2k+1種；

?? ? ? ? 自然數(shù)中：計(jì)數(shù)為買(mǎi)入，偶數(shù)為賣(mài)出

?? ? ? ? 所以二維數(shù)組的定義如下

?? ? ? ? */

? ? ? ? letsize = prices.count

? ? ? ? letstateSize =2*k+1

? ? ? ? vardp: [[Int]] = [[Int]](repeating: [Int](repeating:0, count: stateSize), count: size)

? ? ? ? /*

? ? ? ? step1:確定遞推公式

?? ? ? ? dp[i][1]表示第i天，買(mǎi)入股票的狀態(tài)，并不是說(shuō)一定要在第i天買(mǎi)入股票

?? ? ? ? 第i天買(mǎi)入股票，那么dp[i][1] = dp[i-1][0]-prices[i]

?? ? ? ? 第i天無(wú)操作，而是沿用前一天買(mǎi)入的狀態(tài) dp[i][1] = dp[i-1][1]

?? ? ? ? dp[i][2]表示第i天，賣(mài)出股票的狀態(tài)

?? ? ? ? 第i天賣(mài)出股票 dp[i][2] = dp[i-1][1]+prices[i]

?? ? ? ? 第i天無(wú)操作，而是沿用前一天賣(mài)出的狀態(tài) dp[i][2] = dp[i-1][2]

?? ? ? ? 所以遞推公式如下：

? ? ? ? ? dp[i][j+1] = max(dp[i-1][j+1],dp[i-1][j]-prices[i])

? ? ? ? ? dp[i][j+2] = max(dp[i-1][j+1]+prices[i], dp[i-1][j+2])

?? ? ? ? */

? ? ? ? /*

? ? ? ? step2:初始化

? ? ? ? dp[0][1] = -prices[0]? //第一次買(mǎi)入，

? ? ? ? dp[0][2] = 0? ? //第一次賣(mài)出，賣(mài)出操作一定是獲取利潤(rùn)，整個(gè)股票買(mǎi)賣(mài)最差就是沒(méi)有盈利即全程無(wú)操作現(xiàn)金為0

? ? ? ? dp[0][3] = -prices[0]? //第二次買(mǎi)入，不管怎么樣，手頭上沒(méi)有現(xiàn)金，只要買(mǎi)入，現(xiàn)金就應(yīng)該減少

? ? ? ? dp[0][4] = 0? ? //第二次賣(mài)出，賣(mài)出操作一定是獲取利潤(rùn)，整個(gè)股票買(mǎi)賣(mài)最差就是沒(méi)有盈利即全程無(wú)操作現(xiàn)金為0

?? ? ? ? */

? ? ? ? for?index?in?stride(from:1, to: stateSize, by:2) {

? ? ? ? ? ? dp[0][index] =-prices[0]

? ? ? ? }

? ? ? ? /*

? ??????step3:寫(xiě)循環(huán)體

????????*/

? ? ? ? for?i?in1 ..< size {

? ? ? ? ? ? for?j?in?stride(from:0, to: stateSize-1, by:2) {

? ? ? ? ? ? ? ? dp[i][j+1] =max(dp[i-1][j+1], dp[i-1][j]-prices[i])

? ? ? ? ? ? ? ? dp[i][j+2] =max(dp[i-1][j+1]+prices[i], dp[i-1][j+2])

? ? ? ? ? ? }

? ? ? ? }

? ? ? ? return?dp[size-1][2*k]

? ? }

?? ? 題目鏈接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/

?? ? 給定一個(gè)數(shù)組，它的第 i 個(gè)元素是一支給定的股票在第 i 天的價(jià)格。

?? ? 設(shè)計(jì)一個(gè)算法來(lái)計(jì)算你所能獲取的最大利潤(rùn)。你最多可以完成 兩筆 交易。

?? ? 注意：你不能同時(shí)參與多筆交易（你必須在再次購(gòu)買(mǎi)前出售掉之前的股票）。

?? ? 示例 1:

?? ? 輸入：prices =[3,3,5,0,0,3,1,4]

?? ? 輸出：6

?? ? 解釋?zhuān)涸诘?4 天（股票價(jià)格 = 0）的時(shí)候買(mǎi)入，在第 6 天（股票價(jià)格 = 3）的時(shí)候賣(mài)出，這筆交易所能獲得利潤(rùn) = 3-0 = 3 。隨后，在第 7 天（股票價(jià)格 = 1）的時(shí)候買(mǎi)入，在第 8 天 （股票價(jià)格 = 4）的時(shí)候賣(mài)出，這筆交易所能獲得利潤(rùn) = 4-1 = 3。

?? ? 示例 2：

?? ? 輸入：prices =[1,2,3,4,5]

?? ? 輸出：4

?? ? 解釋?zhuān)涸诘?1 天（股票價(jià)格 = 1）的時(shí)候買(mǎi)入，在第 5 天 （股票價(jià)格 = 5）的時(shí)候賣(mài)出, 這筆交易所能獲得利潤(rùn) = 5-1 = 4。注意你不能在第 1 天和第 2 天接連購(gòu)買(mǎi)股票，之后再將它們賣(mài)出。因?yàn)檫@樣屬于同時(shí)參與了多筆交易，你必須在再次購(gòu)買(mǎi)前出售掉之前的股票。

?? ? 示例 3：

?? ? 輸入：prices =[7,6,4,3,1]

?? ? 輸出：0

?? ? 解釋?zhuān)涸谶@個(gè)情況下, 沒(méi)有交易完成, 所以最大利潤(rùn)為0。

?? ? 示例 4：

?? ? 輸入：prices =[1]

?? ? 輸出：0

?? ? 提示：

?? ? 1 <= prices.length <= 10^5

?? ? 0 <= prices[i] <= 10^5

func?stock3(_prices: [Int]) ->Int{

? ? ? ? let?size = prices.count

? ? ? ? var?dp: [[Int]] = [[Int]](repeating: [Int](repeating:0, count:5), count: size)

? ? ? ? /*

?? ? ? ? 一共有5種狀態(tài)(無(wú)操作0，買(mǎi)入1，賣(mài)出2，買(mǎi)入3，賣(mài)出4)

?? ? ? ? 0:不做任何操作? dp[i][0] = dp[i-1][0]

?? ? ? ? 1:買(mǎi)入 兩種情況前一天無(wú)操作今天買(mǎi)入，沿用前一天狀態(tài)? dp[i][1] = max(dp[i-1][0]-prices[i], dp[i-1][1])

?? ? ? ? 2:賣(mài)出 兩種情況前一天買(mǎi)入今天賣(mài)出，沿用前一天狀態(tài)? dp[i][2] = max(dp[i-1][1]+prices[i] , dp[i-2][2])

?? ? ? ? */

? ? ? ? /*

?? ? ? ? step2:初始化

?? ? ? ? 不做任何操作 dp[0][0] = 0? ? ? ? ? ? //無(wú)操作

?? ? ? ? 第一次買(mǎi)入：dp[0][1] = -prices[0]? ? //第一次買(mǎi)入

?? ? ? ? 第一次賣(mài)出：dp[0][2] = 0? ? ? ? ? ? //第一次賣(mài)出，賣(mài)出操作一定是獲取利潤(rùn)，整個(gè)股票買(mǎi)賣(mài)最差就是沒(méi)有盈利即全程無(wú)操作現(xiàn)金為0

?? ? ? ? 第二次買(mǎi)入：dp[0][3] = -prices[0]? ? //第二次買(mǎi)入，不管怎樣，只要買(mǎi)入現(xiàn)金就會(huì)減少

?? ? ? ? 第二次賣(mài)出：dp[0][4] = 0? ? ? ? ? ? //第二次賣(mài)出，賣(mài)出操作一定是獲取利潤(rùn)，整個(gè)股票買(mǎi)賣(mài)最差就是沒(méi)有盈利即全程無(wú)操作現(xiàn)金為0

?? ? ? ? */

? ? ? ? for?i?in?stride(from:1, to:5, by:2) {

? ? ? ? ? ? dp[0][i] =-prices[0]

? ? ? ? }

? ? ? ? /*

?? ? ? ? step3:寫(xiě)循環(huán)體

?? ? ? ? */

? ? ? ? for?i?in?1 ..< size {

? ? ? ? ? ? for?j?in?stride(from:0, to:4, by:2) {

? ? ? ? ? ? ? ? dp[i][j+1] =max(dp[i-1][j+1], dp[i-1][j]-prices[i])

? ? ? ? ? ? ? ? dp[i][j+2] =max(dp[i-1][j+2], dp[i-1][j+1]+prices[i])

? ? ? ? ? ? }

? ? ? ? }

? ? ? ? return?dp[size-1][4]

? ? }

?題目鏈接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/?? ?

給定一個(gè)整數(shù)數(shù)組，其中第 i 個(gè)元素代表了第 i 天的股票價(jià)格 。?? ?

設(shè)計(jì)一個(gè)算法計(jì)算出最大利潤(rùn)。

在滿(mǎn)足以下約束條件下，你可以盡可能地完成更多的交易（多次買(mǎi)賣(mài)一支股票）:??

? 你不能同時(shí)參與多筆交易（你必須在再次購(gòu)買(mǎi)前出售掉之前的股票）。?? ?

賣(mài)出股票后，你無(wú)法在第二天買(mǎi)入股票 (即冷凍期為 1 天)。?? ?

示例:?? ?

輸入: [1,2,3,0,2]?? ?

輸出: 3?? ?

解釋: 對(duì)應(yīng)的交易狀態(tài)為: [買(mǎi)入, 賣(mài)出, 冷凍期, 買(mǎi)入, 賣(mài)出]

func?stock5(_prices: [Int]) ->Int{

? ? ? ? letsize = prices.count

? ? ? ? //買(mǎi)入，賣(mài)出，冷凍期（三種狀態(tài)）

? ? ? ? var?dp: [[Int]] = [[Int]](repeating: [Int](repeating:0, count:3), count: size)

? ? ? ? /*

?? ? ? ? step1:確定推到公式

?? ? ? ? 持有：

?? ? ? ? 1、前一天就持有? dp[i][0] = dp[i-1][0]

?? ? ? ? 2、前一天不持有，今天買(mǎi)入? dp[i][0] = dp[i-1][1]-prices[i]

?? ? ? ? 不持有：

?? ? ? ? 1、前一天不持有：dp[i][1] = dp[i-1][1]

?? ? ? ? 2、前一天處于冷凍期：dp[i][1] = dp[i-1][2]

?? ? ? ? 冷凍期：（即獲取最大利潤(rùn)）

?? ? ? ? dp[i][2] = dp[i-1][0] + prices[i]

?? ? ? ? 綜合分析推到公式為：

?? ? ? ? dp[i][0] = max(dp[i-1][0],dp[i-1][1] - prices[i])

?? ? ? ? dp[i][1] = max(dp[i-1][1]? dp[i][1] = dp[i-1][2])

?? ? ? ? dp[i][2] = dp[i-1][0]+prices[i]

?? ? ? ? */

? ? ? ? /*

?? ? ? ? step2:初始化

?? ? ? ? 持有,之前沒(méi)有股票，所以買(mǎi)入 dp[0][0] = -prices[0]

?? ? ? ? 不持有，還沒(méi)有買(mǎi)賣(mài)，為0

?? ? ? ? 冷凍期，依賴(lài)于前一天賣(mài)的情況，所以也為0

?? ? ? ? */

? ? ? ? dp[0][0] =-prices[0]? //持有股票

? ? ? ? /*

?? ? ? ? step3:寫(xiě)循環(huán)體

?? ? ? ? */

? ? ? ? for?i?in?1 ..< size {

? ? ? ? ? ? dp[i][0] =max(dp[i-1][1]-prices[i], dp[i-1][0])

? ? ? ? ? ? dp[i][1] =max(dp[i-1][1], dp[i-1][2])

? ? ? ? ? ? dp[i][2] = dp[i-1][0]+prices[i]

? ? ? ? }

? ? ? ? return?max(dp[size-1][1], dp[size-1][2])

? ? }

題目鏈接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/

給定一個(gè)整數(shù)數(shù)組?prices，其中第?i?個(gè)元素代表了第?i?天的股票價(jià)格 ；非負(fù)整數(shù)?fee 代表了交易股票的手續(xù)費(fèi)用。

你可以無(wú)限次地完成交易，但是你每筆交易都需要付手續(xù)費(fèi)。如果你已經(jīng)購(gòu)買(mǎi)了一個(gè)股票，在賣(mài)出它之前你就不能再繼續(xù)購(gòu)買(mǎi)股票了。

返回獲得利潤(rùn)的最大值。

注意：這里的一筆交易指買(mǎi)入持有并賣(mài)出股票的整個(gè)過(guò)程，每筆交易你只需要為支付一次手續(xù)費(fèi)。

示例 1:輸入: prices = [1, 3, 2, 8, 4, 9], fee = 2

輸出: 8

解釋:

能夠達(dá)到的最大利潤(rùn):?

?在此處買(mǎi)入?prices[0] = 1

在此處賣(mài)出 prices[3] = 8

在此處買(mǎi)入 prices[4] = 4

在此處賣(mài)出 prices[5] = 9

總利潤(rùn):?((8 - 1) - 2) + ((9 - 4) - 2) = 8.

func?stock6(_prices:[Int] , _ fee: Int) ->Int{

? ? ? ? /*

? ? step1: 推導(dǎo)公式

? ? ? ? //dp[i][0] 表示第i天持有股票，所得現(xiàn)金

? ? ? ? /*

?? ? ? ? 1、前一天就持有股票，所得現(xiàn)金為前一天持有股票的所得現(xiàn)金 dp[i-1][0]

?? ? ? ? 2、前一天不持有股票，所得現(xiàn)金為前一天持有股票+今天股票的價(jià)格dp[i-1][1]+prices[i]

?? ? ? ? */

? ? ? ? //dp[i][1] 表示第i天不持有股票，所得現(xiàn)金

? ? ? ? /*

?? ? ? ? 1、前一天就持有股票，所得現(xiàn)金為前一天不持有股票的所得現(xiàn)金減今天的股票價(jià)格 dp[i-1][1]-prices[i]

?? ? ? ? 2、前一天不持有股票，所得現(xiàn)金為

? ? ? ? ? ? 前一天不持有股票，那么保持現(xiàn)狀dp[i-1][1]

? ? ? ? ? ? 前一天持有股票，今天賣(mài)出，即：dp[i-1][0]+prices[i]-fee

?? ? ? ? */

?????let?size = prices.count

?????var?dp:[[Int]] = [[Int]](repeating: [Int](repeating:0, count:2), count: size)

? ? ? ? /*

? ? ? ? step2:初始化

????????*/

? ? ? ? dp[0][0] =-prices[0]

? ? ? ? dp[0][1] =0

? ? ? ? /*

? ? ? ? step3:寫(xiě)循環(huán)體

????????*/

?????????for?index?in?1 ..< size {

? ? ? ? ? ? ????dp[index][0] =max(dp[index-1][1]-prices[index], dp[index-1][0])

? ? ? ? ? ? ????dp[index][1] =max(dp[index-1][1], dp[index-1][0]+prices[index]-fee)

? ? ? ? }

?????????return?dp[size-1][1]

? ? }