算法合集之淺析信息學(xué)中的“分”與“合”(存儲版)
【正文】 引理一 原問題的任意一組解都可以由 K組不相交的子問題的解組成。 N,K限制下最優(yōu)化問題 → N,K,Len限制下存在性問題 規(guī)模為 n的問題 → 規(guī)模為 n1的問題 [例三 ]最優(yōu)序列 ?給定一個長度為 N的正整數(shù)序列。 “分治法”是運用“分”與“合”思想方法解題的重要應(yīng)用，此外，“分”與“合”的思想方法還有更多、更廣泛的應(yīng)用。 ? 設(shè) dp[i]表示前 i個元素，在滿足題意的前提下選出的最大和 dp[i]=max(dp[i1],dp[iM]+value[i]) i≥M dp[i]=max(dp[i1],value[i]) 0iM dp[0]=0 [例三 ]最優(yōu)序列 —— 進(jìn)一步分析 子問題 原問題 是否可以通過求解 K次的子問題從而解決原題呢 ? 1 K [例三 ]最優(yōu)序列 —— 進(jìn)一步分析 ? 命題 原問題的解集等價于由 K組互不相交的子問題的解組成的解集。 總結(jié) 分 合 對立 統(tǒng)一 “ 分”的思想幫助我們
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1