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