當前位置:股票大全官網 - 股票投資 - 如何定義dp表2020-10-04(不允許禁止旋轉)

如何定義dp表2020-10-04(不允許禁止旋轉)

有關dp基礎知識,請參見dp基礎知識。

要解決dp問題,首先要定義dp表,然後找到相應的狀態轉移方程。如何定義dp表成為解決問題的前提。

如何定義dp表,

綜上分析,其實不管是多態dp還是單態dp,dp表都要正確描述兩方面的信息,當前問題規模+當前問題狀態。只有單個狀態dp具有單個狀態,因此可以從描述中省略。

【尺度】可以是壹維,二維,三維等等,看具體問題。也就是

【狀態】也可以是壹維(單態)、二維、三維等等(多態)。也就是

股票系列的共同問題是,

解決方案:

首先,我直觀的感覺到,目前能獲得的最大利潤,必然與這之前股票的交易情況有關,不同尺度之間應該存在狀態轉移關系,可以是dp。而dp就是暴力,備忘錄裏暴力多了,暴力就是嘗試每壹種交易情境,總能得到答案。這樣dp基本就能做到了。

給定壹個數組,它的第I個元素是給定股票在第I天的價格。

設計壹個算法,計算出妳能獲得的最大利潤。妳可以完成盡可能多的交易(多次買賣壹只股票)

給定壹個數組,它的第I個元素是給定股票在第I天的價格。

設計壹個算法,計算出妳能獲得的最大利潤。您最多可以完成k筆交易。

註意:您不能同時參與多個交易(您必須先賣出之前的股票,然後才能再次買入)

把買當做交易的標誌。

把賣當交易的標誌。