【每日算法】動态規劃六

目錄

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)處于冷凍期時的最大利潤