[其它技巧]lecture_04動(dòng)態(tài)規(guī)劃-文庫(kù)吧資料
2024-10-24 22:30本頁(yè)面
【正文】 試想一下： 2021/11/10 16 拒絕 暴力， 倡導(dǎo) 和諧～ 2021/11/10 17 從頂點(diǎn)出發(fā)時(shí)到底向左走還是向右走應(yīng)取決于是從左走能取到最大值還是從右走能取到最大值，只要左右兩道路徑上的最大值求出來(lái)了才能作出決策。 重點(diǎn)分析 —— n的情況： 2021/11/10 12 從上述 n=4的分析過(guò)程中，我們發(fā)現(xiàn)： m條直線的交點(diǎn)方案數(shù) =（ mr）條平行線與 r條直線交叉的交點(diǎn)數(shù) + r條直線本身的交點(diǎn)方案 =（ mr） *r+r條之間本身的交點(diǎn)方案數(shù)（ 0=rm） 重點(diǎn)分析 —— n的情況： 2021/11/10 13 一、數(shù)塔問(wèn)題 有形如下圖所示的數(shù)塔，從頂部出發(fā)，在每一結(jié)點(diǎn)可以選擇向左走或是向右走，一直走到底層，要求找出一條路徑，使路徑上的值最大。 樣例輸入 4 樣例輸出 0 3 4 5 6 2021/11/10 7 初步分析 : 我們知道 : n條直線互不平行且無(wú)三線共點(diǎn)的最多交點(diǎn)數(shù) max=1+2+…… (n1)=n(n1)/2, 但本題不這么簡(jiǎn)單，因?yàn)閱?wèn)題問(wèn)的是：這些直線有 多少種 不同的交點(diǎn)數(shù)？ 2021/11/10 8 思考 2分鐘 :如何解決 ? 2021/11/10 9 然后， 假設(shè) =n1的情況都已經(jīng)知道 —— 分析思路 —— 首先， 容易列舉出 N=1,2,3的情況： 0 0， 1 0， 2， 3 2021/11/10 10 先來(lái)看個(gè)統(tǒng)計(jì)的方法： 假設(shè)一共有 n=a+b條直線 （即 n條直線分成 2組，分別為 a條和 b條） 則總的交點(diǎn)數(shù) = a內(nèi)的交點(diǎn)數(shù) ＋ b內(nèi)的交點(diǎn)數(shù) ＋ a， b之間的交點(diǎn)數(shù) 重點(diǎn)分析 —— n的情況： 2021/11/10 11 我們來(lái)分析加入第 N條直線的情況
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1