天天看點

【每日算法】動态規劃六

目錄

1014.最佳觀光組合

121.買賣股票的最佳時機

122.買賣股票的最佳時機ii

309.最佳買賣股票時機含冷凍期

難度[中等]

已知:f(i,j)=values[i] + i + values[j] - j (i小于j),求f(i,j)最大

f(i,j)最大,在j之前的values[i]+i 最大,與目前的values[j]-j 最大值

定義兩個數組dp_plus[j]為j之前最大值,dp[j]要求的結果

難度[簡單]

定義f(x)為第x天所能擷取的最大利潤,最大利潤有買入時的價格,和當天價格的內插補點

定義買入的價格為ru,所有f(x)=max(prices[x]-ru,f(x-1))

ru的值為min(ru,prices[x])

第一種:貪心算法

貪心算法隻求局部最優解,再把每個局部最優的

遇到比前一個價格高的就賣出,累計求和

第二種: 動态規劃

因為可以頻繁買入賣出,是以針對每一天的股票都有可能持有或不持有,是以定義兩個狀态,f(i,(0|1)),表示持有當天或不持有時擷取的最大利潤

利潤最大時為最後一天時把手裡的股票給賣出去<code>dp[-1][0]</code>

f(i)為第i天的最大利潤,因為可以多次買賣,是以第i天有兩種狀态f(i,0)持有股票時的最大利潤,和f(i,1)不持有股票時的最大利潤;又因為在賣出的第二天是處于冷凍期的,無法進行交易,是以還需要一個狀态f(i,2)處于冷凍期時的最大利潤

繼續閱讀