算法合集之淺析信息學中的“分”與“合”(留存版)
【正文】 O(2MN)！ 100 1000) [例三 ]最優(yōu)序列 —— “ 分”繁為簡 ?動態(tài)規(guī)劃之所以不可行，原因在于 —— 題目中 K和 M的范圍太大了！ ?利用“分”的思想，我們嘗試限制 K，令 K=1，也就是對于長度為 M的子串，最多只選一個元素作為原題的一個子問題： [例三 ]最優(yōu)序列 —— 子問題 ?給定一個長度為 N的正整數序列。 總結 分 合 對立 統(tǒng)一 “ 分”的思想幫助我們迅速地切入問題核心，但若過分細化則會使問題太過凌亂，失去求解的方向；而“合”的思想則以線串珠，使各種紛雜無序的問題具有了整體性。 “分治法”是運用“分”與“合”思想方法解題的重要應用，此外，“分”與“合”的思想方法還有更多、更廣泛的應用。 ? 引理一 原問題的任意一組解都可以由 K組不相交的子問題的解組成。 [例三 ]最優(yōu)序列 —— 進一步分析 ?題目中存在著一個潛條件，即： 每個元素只能被選一次 ?若直接套用 K次動態(tài)規(guī)劃來求解，有可能導致某個元素被取多次，無法滿足題目中的這個條件。 ?合 ?
教學課件相關推薦
鄂ICP備17016276號-1