股票問(wèn)題，狀態(tài)轉(zhuǎn)移方程需要分析出有幾個(gè)維度，就需要幾個(gè)維度去列狀態(tài)轉(zhuǎn)移方程
買賣股票的最佳時(shí)機(jī)
- 給定一個(gè)數(shù)組 prices ，它的第 i 個(gè)元素 prices[i] 表示一支給定股票第 i 天的價(jià)格。
你只能選擇 某一天 買入這只股票，并選擇在 未來(lái)的某一個(gè)不同的日子 賣出該股票。設(shè)計(jì)一個(gè)算法來(lái)計(jì)算你所能獲取的最大利潤(rùn)。
返回你可以從這筆交易中獲取的最大利潤(rùn)。如果你不能獲取任何利潤(rùn)，返回 0 。
分析：由于你選擇在哪天賣出都是最精明選擇，那這里明顯只有在第幾天賣出，有最大利潤(rùn)，可以知道只有一個(gè)維度。
data[index] index表示哪天，data[index] 表示哪天賣出可以得到最大利潤(rùn)。
func maxProfit(_ prices: [Int]) -> Int {
if prices.count <= 1 {
return 0
}
// 存儲(chǔ)當(dāng)前和最小值之差的最大現(xiàn)金數(shù)。
var data = [Int](repeating: 0, count: prices.count)
var minPrice = prices[0]
for x in 1 ..< prices.count {
// 和當(dāng)前值比較，誰(shuí)小，更新
minPrice = min(prices[x], minPrice)
// 今天得到現(xiàn)金數(shù) 可能是 昨天賣出去得到，或者今天賣出得到的，賣出意味著需要減去最小值
data[x] = Swift.max(data[x - 1] , prices[x] - minPrice)
}
return data[prices.count - 1]
}
122.給定一個(gè)數(shù)組 prices ，其中 prices[i] 是一支給定股票第 i 天的價(jià)格。
設(shè)計(jì)一個(gè)算法來(lái)計(jì)算你所能獲取的最大利潤(rùn)。你可以盡可能地完成更多的交易（多次買賣一支股票）。
注意：你不能同時(shí)參與多筆交易（你必須在再次購(gòu)買前出售掉之前的股票）。
分析：由于不能同時(shí)參與多筆交易，表示不能一次多次買入賣出，但在整個(gè)交易過(guò)程里是可以多次買入-》賣出-》買入-》賣出的。
方便表示可以定義data[index][x] index表示哪天，x表示是買入還是賣出，只有兩種情況，可以用0，1表示。
func maxProfit(_ prices: [Int]) -> Int {
if prices.count == 0 {
return 0
}
// 理解比較難，就是需要記住當(dāng)前的現(xiàn)金數(shù)只有兩種狀態(tài)，分買進(jìn)股票，就是現(xiàn)金相對(duì)昨天減少，賣出股票就是相對(duì)昨天增加，
// 這樣就可以定義0 表示賣出，現(xiàn)金增加的做法，1表示買進(jìn)，現(xiàn)金減少的做法
var data = [[Int]](repeating: [0,0], count: prices.count)
// 一開始，計(jì)算賣出，現(xiàn)金增加狀態(tài)時(shí)，既沒(méi)買，也沒(méi)賣，所以一開始現(xiàn)金數(shù)0
// 而一開始，對(duì)于另外一種可能買進(jìn)，現(xiàn)金減少狀態(tài)，那就需要買進(jìn)，所以現(xiàn)金數(shù)為第一天買入的股票價(jià)格，為負(fù)
data[0][0] = 0
data[0][1] = -prices[0]
for (index, x) in prices.enumerated() {
if index > 0 {
data[index][0] = Swift.max(data[index - 1][0], data[index - 1][1] + prices[index])
data[index][1] = Swift.max(data[index - 1][1], data[index - 1][0] - prices[index])
}
}
return data[prices.count - 1][0]
}
123.給定一個(gè)數(shù)組，它的第 i 個(gè)元素是一支給定的股票在第 i 天的價(jià)格。
設(shè)計(jì)一個(gè)算法來(lái)計(jì)算你所能獲取的最大利潤(rùn)。你最多可以完成 兩筆 交易。
注意：你不能同時(shí)參與多筆交易（你必須在再次購(gòu)買前出售掉之前的股票）。
分析：由于還是不能同時(shí)參與多筆交易，但限制了只能最多交易兩次。
所以相當(dāng)于哪天，是買進(jìn)還是賣出，到目前為止賣出幾次，也就是有三個(gè)維度
可以定義data[index][x][y] index表示哪天，x表示是買入還是賣出，只有兩種情況，可以用0，1表示,y表示賣了幾次，只有沒(méi)賣過(guò)，賣了一次，賣了兩次，所以可以用0，1，2表示。
func maxProfit(_ prices: [Int]) -> Int {
if prices.count <= 1 {
return 0
}
// 三個(gè)維度，天數(shù)，是否買進(jìn)1/賣出0，買了幾次
var data = [[[Int]]](repeating: [[Int]](repeating: [0,0,0], count: 2), count: prices.count)
// 第一天，沒(méi)賣出，賣次數(shù)0 ，所以現(xiàn)金為0
data[0][0][0] = 0
// 第一天，沒(méi)賣出，賣次數(shù)1 ，不可能出現(xiàn)，所以默認(rèn)為最小值
data[0][0][1] = -99999
// 第一天，沒(méi)賣出，賣次數(shù)2 ，不可能出現(xiàn)，所以默認(rèn)為最小值
data[0][0][2] = -99999
// 第一天，買進(jìn)，賣次數(shù)0 ，所以取prices[0]加負(fù)號(hào)，減少現(xiàn)金
data[0][1][0] = -prices[0]
// 第一天，買進(jìn)，賣次數(shù)1 ，同天只能操作買進(jìn)/賣出，不能一天同時(shí)操作買進(jìn)和賣出，所以不可能出現(xiàn)，所以默認(rèn)為最小值
data[0][1][1] = -99999
// 第一天，買進(jìn)，賣次數(shù)2 ，同天只能操作買進(jìn)/賣出，不能一天同時(shí)操作買進(jìn)和賣出，那就更不可能有兩次賣出，所以不可能出現(xiàn)，所以默認(rèn)為最小值
data[0][1][2] = -99999
for index in 1 ..< prices.count {
// 沒(méi)做任何操作，所以為0
data[index][0][0] = 0
data[index][0][1] = Swift.max(data[index - 1][0][1], data[index - 1][1][0] + prices[index])
data[index][0][2] = Swift.max(data[index - 1][0][2], data[index - 1][1][1] + prices[index])
data[index][1][0] = Swift.max(data[index - 1][1][0], data[index - 1][0][0] - prices[index])
data[index][1][1] = Swift.max(data[index - 1][1][1], data[index - 1][0][1] - prices[index])
data[index][1][2] = -99999
}
return Swift.max(Swift.max(data[prices.count - 1][0][2], data[prices.count - 1][0][1]), 0)
}
