要解決dp問題,首先要定義dp表,然後找到相應的狀態轉移方程。如何定義dp表成為解決問題的前提。
如何定義dp表,
綜上分析,其實不管是多態dp還是單態dp,dp表都要正確描述兩方面的信息,當前問題規模+當前問題狀態。只有單個狀態dp具有單個狀態,因此可以從描述中省略。
【尺度】可以是壹維,二維,三維等等,看具體問題。也就是
【狀態】也可以是壹維(單態)、二維、三維等等(多態)。也就是
股票系列的共同問題是,
解決方案:
首先,我直觀的感覺到,目前能獲得的最大利潤,必然與這之前股票的交易情況有關,不同尺度之間應該存在狀態轉移關系,可以是dp。而dp就是暴力,備忘錄裏暴力多了,暴力就是嘗試每壹種交易情境,總能得到答案。這樣dp基本就能做到了。
給定壹個數組,它的第I個元素是給定股票在第I天的價格。
設計壹個算法,計算出妳能獲得的最大利潤。妳可以完成盡可能多的交易(多次買賣壹只股票)
給定壹個數組,它的第I個元素是給定股票在第I天的價格。
設計壹個算法,計算出妳能獲得的最大利潤。您最多可以完成k筆交易。
註意:您不能同時參與多個交易(您必須先賣出之前的股票,然後才能再次買入)
把買當做交易的標誌。
把賣當交易的標誌。