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