188. Best Time to Buy and Sell Stock IV
看著知道是dp問題糠雨，但是找不出狀態(tài)和轉(zhuǎn)移方程
狀態(tài)是dp[i][j] 針對(duì)前j各元素進(jìn)行最多i次交易可以獲得的最大利益。
dp[0][j] = 0 如果是0次交易則獲得0
dp[i][0] = 0 如果針對(duì)第一個(gè)值prices[0]徘跪，因?yàn)椴荒軌蚪灰赘恃瑒t獲得利益為0
dp[i][j] = max(
- dp[i][j-1] 不利用此次prices[j]所能獲得的最大利益
- for k in 0..j-1:
dp[i-1][k-1] + price[j] - price[k] 利用此次prices[j]，則prices[j]肯定是做為賣出點(diǎn)垮庐，且獲得的利益是 針對(duì) k-1進(jìn)行i-1次交易所獲得的最大值松邪，加上這一次交易k為買入點(diǎn)，j為賣出點(diǎn)所獲得的利益
)
class Solution(object):
def maxProfit(self, k, prices):
"""
:type k: int
:type prices: List[int]
:rtype: int
"""
# dp[i][j] 對(duì)前j個(gè)元素進(jìn)行最多i次transactions獲取的最大值
if k <= 0:
return 0
if len(prices) <= 1:
return 0
res = 0
if k >= len(prices)/2:
base = prices[0]
for p in prices[1:]:
if p - base > 0:
res += p - base
base = p
return res
dp = [[0 for _ in range(len(prices))] for _ in range(k+1)]
for i in range(1, k+1):
localmax = dp[i-1][0] - prices[0]
for j in range(1, len(prices)):
dp[i][j] = max(dp[i][j-1], prices[j] + localmax)
localmax = max(localmax, dp[i-1][j-1] - prices[j])
return dp[k][len(prices)-1]
