樹型動規

樹型動規,是基於樹形數據結構的多階段決策算法,以父節點作為階段,程式簡潔明了。

基於樹形數據結構的多階段決策算法,以父節點作為階段,程式簡潔明了
套用條件:
Ø 整個圖是一個樹狀的結構或者可以轉化為樹狀的結構。
Ø 對於每個根節點的狀態,跟且僅跟所屬的孩子(大多為2個)有牽連關係。也就是說,父親對孩子沒有影響。
Ø 狀態可以簡單的表示
Ø 有重疊子問題(可以沒有,不過那樣套用dp就沒有意義了)
不過以上條件所具備的題未必一定用dp,可以用其余巧妙的算法做。

相關詞條

相關搜尋

熱門詞條

聯絡我們