算法合集之正難則反–淺談逆向思維在解題中的應(yīng)用(參考版)
2024-10-19 20:32本頁面
【正文】 例三、 Building Towers 讓我們來看看逆向動態(tài)規(guī)劃的精彩表現(xiàn)： N H M 正向動態(tài)規(guī)劃所需要處理的狀態(tài)量 逆向動態(tài)規(guī)劃中存儲的狀態(tài)量 正逆向動態(tài)規(guī)劃狀態(tài)數(shù)比值 1000 40 10 1202100 3055 1500 50 10 2625000 5371 1200 60 10 2880000 49875 1500 60 10 3600000 38018 總結(jié) 例一 補(bǔ)集轉(zhuǎn)化思想 例二 參變量法 例三 逆向動態(tài)規(guī)劃 總結(jié) 以退為進(jìn) 避其鋒芒 攻其軟肋 打破思維定勢 反彈琵琶成新曲 Thank You! 。 2)在類似于本題的計(jì)數(shù)問題中，可以采用部分記憶化的方法，即只記錄那些比較容易被多次搜索到的狀態(tài)。 如果每個狀態(tài)用一個 double來保存信息，則至少需要 80M的內(nèi)存 不論是時(shí)間復(fù)雜度，還是空間復(fù)雜度，都讓人難以接受。(*m a x)(EeeEeeSEVC TtCtO例二、 Greedy Path 我們做一個猜想 ： 如果有 o (t*)=0， 也就是存在 C* = (V*,E*) ∈ S 滿足 ： ?????***Ee eEe eTCt我們認(rèn)為 C*就是最優(yōu)回路！ 證明 ： 如果存在另一條回路 C1=(V1,E1) ∈ S更優(yōu) 則 *)()(*0*11111 toTtCtTCtEe eEe eEe eEe e ??????
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1