算法合集之正難則反–淺談逆向思維在解題中的應(yīng)用-資料下載頁(yè)
2025-10-07 20:32本頁(yè)面
【正文】 容易看出，這個(gè)動(dòng)態(tài)規(guī)劃方程一共涉及了N*M*K個(gè)狀態(tài)，最大約為 60*70*2400 = 10M。 如果每個(gè)狀態(tài)用一個(gè) double來(lái)保存信息，則至少需要 80M的內(nèi)存 不論是時(shí)間復(fù)雜度，還是空間復(fù)雜度，都讓人難以接受。 例三、 Building Towers 將規(guī)劃的順序作一個(gè)反轉(zhuǎn) ， 有什么好處呢 ？ 記憶化因子 自頂向下的搜索算法 逆向 動(dòng)態(tài)規(guī)劃 自底向上的動(dòng)態(tài)規(guī)劃算法 例三、 Building Towers 逆向動(dòng)態(tài)規(guī)劃的好處在于： 1)自頂向下的看問(wèn)題，有 “ 一覽眾山小 ” 的開(kāi)闊視野，可以順利地為如何搜，先搜什么后搜什么，以及如何剪枝等作合理的布局。 2)在類(lèi)似于本題的計(jì)數(shù)問(wèn)題中，可以采用部分記憶化的方法，即只記錄那些比較容易被多次搜索到的狀態(tài)。這樣一來(lái)，減少了存儲(chǔ)的狀態(tài)量，加快了查詢(xún)的速度。 例三、 Building Towers 讓我們來(lái)看看逆向動(dòng)態(tài)規(guī)劃的精彩表現(xiàn)： N H M 正向動(dòng)態(tài)規(guī)劃所需要處理的狀態(tài)量 逆向動(dòng)態(tài)規(guī)劃中存儲(chǔ)的狀態(tài)量 正逆向動(dòng)態(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)化思想 例二 參變量法 例三 逆向動(dòng)態(tài)規(guī)劃 總結(jié) 以退為進(jìn) 避其鋒芒 攻其軟肋 打破思維定勢(shì) 反彈琵琶成新曲 Thank You!
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1