動態(tài)規(guī)劃
使用場景：重復(fù)子問題
步驟：
1、定義公式
2诀紊、初始化變量
3述暂、寫循環(huán)體
? ? ?給定一個數(shù)組 prices ，它的第?i 個元素?prices[i] 表示一支給定股票第 i 天的價格阿迈。
?? ? 你只能選擇 某一天 買入這只股票，并選擇在 未來的某一個不同的日子 賣出該股票轧叽。設(shè)計一個算法來計算你所能獲取的最大利潤苗沧。
?? ? 返回你可以從這筆交易中獲取的最大利潤。如果你不能獲取任何利潤炭晒，返回 0 崎页。
?? ? 輸入：[7,1,5,3,6,4]
?? ? 輸出：5
?? ? 解釋：在第 2 天（股票價格 = 1）的時候買入，在第 5 天（股票價格 = 6）的時候賣出腰埂，最大利潤 = 6-1 = 5 飒焦。
? ? ? ? ? 注意利潤不能是 7-1 = 6, 因為賣出價格需要大于買入價格；同時屿笼，你不能在買入前賣出股票牺荠。
? ? func?stock(?_prices : [Int]) ?-> Int {
? ? ? ? let?size = prices.count
? ? ? ? var?dp: [[Int]] = [[Int]](repeating: [Int](repeating:0, count:2), count: size)
? ? ? ? /*
?? ? ? ? step1:推導(dǎo)公式
?? ? ? ? 定義一個二維數(shù)組，用來存放當(dāng)天股票的狀態(tài)
?? ? ? ? 0表示當(dāng)天持有股票
?? ? ? ? 1表示當(dāng)天不持有股票
?? ? ? ? 持有股票的狀態(tài)有兩種情況驴一；1休雌，前一天就持有，保持狀態(tài) 2肝断，前一天不持有杈曲，當(dāng)天買入
?? ? ? ? 不持有股票的狀態(tài)有兩種情況；1胸懈，前一天不持有担扑，保持狀態(tài) 2，前一天持有趣钱，當(dāng)天賣出
?? ? ? ? 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:初始化
?? ? ? ? 第一天持有股票涌献，買入就需要花費，所以：dp[0][0] = -prices[0]
?? ? ? ? 第一天不持有股票首有，第一天不能賣出燕垃，所以：dp[0][1] = 0
?? ? ? ? step3:寫循環(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]
? ? }
????買賣股票的最佳時機2
?? ? https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/
?? ? 給定一個數(shù)組，它的第?i 個元素是一支給定股票第 i 天的價格井联。
?? ? 設(shè)計一個算法來計算你所能獲取的最大利潤卜壕。你可以盡可能地完成更多的交易（多次買賣一支股票）。
?? ? 注意：你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）烙常。
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)金為前一天持有股票+今天股票的價格dp[i-1][1]+prices[i]
?? ? ? ? */
? ? ? ? //dp[i][1] 表示第i天不持有股票蝗锥，所得現(xiàn)金
? ? ? ? /*
?? ? ? ? 1跃洛、前一天就持有股票，所得現(xiàn)金為前一天不持有股票的所得現(xiàn)金減今天的股票價格 dp[i-1][1]-prices[i]
?? ? ? ? 2终议、前一天不持有股票汇竭，所得現(xiàn)金為
? ? ? ? ? ? 前一天不持有股票，那么保持現(xiàn)狀dp[i-1][1]
? ? ? ? ? ? 前一天持有股票穴张，今天賣出细燎，即：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:寫循環(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/
?? ? 給定一個整數(shù)數(shù)組 prices ，它的第 i 個元素 prices[i]是一支給定的股票在第 i 天的價格皂甘。
?? ? 設(shè)計一個算法來計算你所能獲取的最大利潤玻驻。你最多可以完成 k 筆交易。
?? ? 注意：你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）偿枕。
?? ? 示例 ：
?? ? 輸入：k = 2, prices =[3,2,6,5,0,3]
?? ? 輸出：7
?? ? 解釋：在第 2 天 (股票價格 = 2) 的時候買入璧瞬，在第 3 天 (股票價格 = 6) 的時候賣出, 這筆交易所能獲得利潤 = 6-2 = 4。隨后渐夸，在第 5 天 (股票價格 = 0) 的時候買入，在第 6 天 (股票價格 = 3) 的時候賣出, 這筆交易所能獲得利潤 = 3-0 = 3 。
func?stock4(?_?prices: [Int],?_k :Int) -> Int {
? ? ? ? /*
?? ? ? ? 因為設(shè)計到最多次數(shù)k稳衬，所以定義一個二維數(shù)組香缺，使用j表示當(dāng)天的狀態(tài)
?? ? ? ? 比如：k=2，那么就最多有兩次買入苫幢、兩次賣出 還有可能不操作访诱，所以用
?? ? ? ? 0表示不操作 1買入 2賣出 3買入 4賣出，那么當(dāng)天的狀態(tài)就有2k+1種韩肝；
?? ? ? ? 自然數(shù)中：計數(shù)為買入盐数，偶數(shù)為賣出
?? ? ? ? 所以二維數(shù)組的定義如下
?? ? ? ? */
? ? ? ? letsize = prices.count
? ? ? ? letstateSize =2*k+1
? ? ? ? vardp: [[Int]] = [[Int]](repeating: [Int](repeating:0, count: stateSize), count: size)
? ? ? ? /*
? ? ? ? step1:確定遞推公式
?? ? ? ? dp[i][1]表示第i天，買入股票的狀態(tài)伞梯，并不是說一定要在第i天買入股票
?? ? ? ? 第i天買入股票玫氢，那么dp[i][1] = dp[i-1][0]-prices[i]
?? ? ? ? 第i天無操作，而是沿用前一天買入的狀態(tài) dp[i][1] = dp[i-1][1]
?? ? ? ? dp[i][2]表示第i天谜诫，賣出股票的狀態(tài)
?? ? ? ? 第i天賣出股票 dp[i][2] = dp[i-1][1]+prices[i]
?? ? ? ? 第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]? //第一次買入，
? ? ? ? dp[0][2] = 0? ? //第一次賣出喻旷，賣出操作一定是獲取利潤生逸，整個股票買賣最差就是沒有盈利即全程無操作現(xiàn)金為0
? ? ? ? dp[0][3] = -prices[0]? //第二次買入，不管怎么樣，手頭上沒有現(xiàn)金槽袄，只要買入烙无，現(xiàn)金就應(yīng)該減少
? ? ? ? dp[0][4] = 0? ? //第二次賣出，賣出操作一定是獲取利潤遍尺，整個股票買賣最差就是沒有盈利即全程無操作現(xiàn)金為0
?? ? ? ? */
? ? ? ? for?index?in?stride(from:1, to: stateSize, by:2) {
? ? ? ? ? ? dp[0][index] =-prices[0]
? ? ? ? }
? ? ? ? /*
? ??????step3:寫循環(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/
?? ? 給定一個數(shù)組截酷，它的第 i 個元素是一支給定的股票在第 i 天的價格。
?? ? 設(shè)計一個算法來計算你所能獲取的最大利潤乾戏。你最多可以完成 兩筆 交易迂苛。
?? ? 注意：你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）。
?? ? 示例 1:
?? ? 輸入：prices =[3,3,5,0,0,3,1,4]
?? ? 輸出：6
?? ? 解釋：在第 4 天（股票價格 = 0）的時候買入鼓择，在第 6 天（股票價格 = 3）的時候賣出三幻，這筆交易所能獲得利潤 = 3-0 = 3 。隨后呐能，在第 7 天（股票價格 = 1）的時候買入念搬，在第 8 天 （股票價格 = 4）的時候賣出，這筆交易所能獲得利潤 = 4-1 = 3摆出。
?? ? 示例 2：
?? ? 輸入：prices =[1,2,3,4,5]
?? ? 輸出：4
?? ? 解釋：在第 1 天（股票價格 = 1）的時候買入锁蠕，在第 5 天 （股票價格 = 5）的時候賣出, 這筆交易所能獲得利潤 = 5-1 = 4。注意你不能在第 1 天和第 2 天接連購買股票懊蒸，之后再將它們賣出荣倾。因為這樣屬于同時參與了多筆交易，你必須在再次購買前出售掉之前的股票骑丸。
?? ? 示例 3：
?? ? 輸入：prices =[7,6,4,3,1]
?? ? 輸出：0
?? ? 解釋：在這個情況下, 沒有交易完成, 所以最大利潤為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)(無操作0，買入1通危，賣出2铸豁，買入3，賣出4)
?? ? ? ? 0:不做任何操作? dp[i][0] = dp[i-1][0]
?? ? ? ? 1:買入 兩種情況前一天無操作今天買入菊碟，沿用前一天狀態(tài)? dp[i][1] = max(dp[i-1][0]-prices[i], dp[i-1][1])
?? ? ? ? 2:賣出 兩種情況前一天買入今天賣出节芥，沿用前一天狀態(tài)? dp[i][2] = max(dp[i-1][1]+prices[i] , dp[i-2][2])
?? ? ? ? */
? ? ? ? /*
?? ? ? ? step2:初始化
?? ? ? ? 不做任何操作 dp[0][0] = 0? ? ? ? ? ? //無操作
?? ? ? ? 第一次買入：dp[0][1] = -prices[0]? ? //第一次買入
?? ? ? ? 第一次賣出：dp[0][2] = 0? ? ? ? ? ? //第一次賣出，賣出操作一定是獲取利潤逆害，整個股票買賣最差就是沒有盈利即全程無操作現(xiàn)金為0
?? ? ? ? 第二次買入：dp[0][3] = -prices[0]? ? //第二次買入头镊，不管怎樣，只要買入現(xiàn)金就會減少
?? ? ? ? 第二次賣出：dp[0][4] = 0? ? ? ? ? ? //第二次賣出魄幕，賣出操作一定是獲取利潤相艇，整個股票買賣最差就是沒有盈利即全程無操作現(xiàn)金為0
?? ? ? ? */
? ? ? ? for?i?in?stride(from:1, to:5, by:2) {
? ? ? ? ? ? dp[0][i] =-prices[0]
? ? ? ? }
? ? ? ? /*
?? ? ? ? step3:寫循環(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/?? ?
給定一個整數(shù)數(shù)組，其中第 i 個元素代表了第 i 天的股票價格 纯陨。?? ?
設(shè)計一個算法計算出最大利潤坛芽。
在滿足以下約束條件下留储，你可以盡可能地完成更多的交易（多次買賣一支股票）:??
? 你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）。?? ?
賣出股票后咙轩，你無法在第二天買入股票 (即冷凍期為 1 天)获讳。?? ?
示例:?? ?
輸入: [1,2,3,0,2]?? ?
輸出: 3?? ?
解釋: 對應(yīng)的交易狀態(tài)為: [買入, 賣出, 冷凍期, 買入, 賣出]
func?stock5(_prices: [Int]) ->Int{
? ? ? ? letsize = prices.count
? ? ? ? //買入，賣出活喊，冷凍期（三種狀態(tài)）
? ? ? ? var?dp: [[Int]] = [[Int]](repeating: [Int](repeating:0, count:3), count: size)
? ? ? ? /*
?? ? ? ? step1:確定推到公式
?? ? ? ? 持有：
?? ? ? ? 1丐膝、前一天就持有? dp[i][0] = dp[i-1][0]
?? ? ? ? 2、前一天不持有胧弛，今天買入? 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]
?? ? ? ? 冷凍期：（即獲取最大利潤）
?? ? ? ? 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:初始化
?? ? ? ? 持有,之前沒有股票结缚，所以買入 dp[0][0] = -prices[0]
?? ? ? ? 不持有，還沒有買賣软棺，為0
?? ? ? ? 冷凍期红竭，依賴于前一天賣的情況，所以也為0
?? ? ? ? */
? ? ? ? dp[0][0] =-prices[0]? //持有股票
? ? ? ? /*
?? ? ? ? step3:寫循環(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/
給定一個整數(shù)數(shù)組?prices喘落，其中第?i?個元素代表了第?i?天的股票價格 茵宪；非負(fù)整數(shù)?fee 代表了交易股票的手續(xù)費用。
你可以無限次地完成交易瘦棋，但是你每筆交易都需要付手續(xù)費稀火。如果你已經(jīng)購買了一個股票，在賣出它之前你就不能再繼續(xù)購買股票了赌朋。
返回獲得利潤的最大值凰狞。
注意：這里的一筆交易指買入持有并賣出股票的整個過程，每筆交易你只需要為支付一次手續(xù)費沛慢。
示例 1:輸入: prices = [1, 3, 2, 8, 4, 9], fee = 2
輸出: 8
解釋:
能夠達(dá)到的最大利潤:?
?在此處買入?prices[0] = 1
在此處賣出 prices[3] = 8
在此處買入 prices[4] = 4
在此處賣出 prices[5] = 9
總利潤:?((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)金為前一天持有股票+今天股票的價格dp[i-1][1]+prices[i]
?? ? ? ? */
? ? ? ? //dp[i][1] 表示第i天不持有股票躺苦，所得現(xiàn)金
? ? ? ? /*
?? ? ? ? 1身腻、前一天就持有股票，所得現(xiàn)金為前一天不持有股票的所得現(xiàn)金減今天的股票價格 dp[i-1][1]-prices[i]
?? ? ? ? 2匹厘、前一天不持有股票霸株，所得現(xiàn)金為
? ? ? ? ? ? 前一天不持有股票，那么保持現(xiàn)狀dp[i-1][1]
? ? ? ? ? ? 前一天持有股票集乔，今天賣出去件，即：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:寫循環(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]
? ? }
