其它技巧lecture動態(tài)規(guī)劃課件

1、2022/9/291今天，你 了嗎？AC2022/9/271今天，你 了嗎？AC2022/9/292每周一星（3）：混沌的云Knight 2022/9/272每周一星（3）：混沌的云Knight 2022/9/293第四講動態(tài)規(guī)劃(1) （Dynamic programming）2022/9/273第四講動態(tài)規(guī)劃(1) 2022/9/294先熱身一下2022/9/274先熱身一下2022/9/295(1466)計算直線的交點(diǎn)數(shù)問題描述： 平面上有n條直線，且無三線共點(diǎn)，問這些直線能有多少種不同交點(diǎn)數(shù)。輸入：n（n=20）輸出：每個測試實(shí)例對應(yīng)一行輸出，從小到大列出所有相交方案，其中每個數(shù)為可能

2、的交點(diǎn)數(shù)。樣例輸入4樣例輸出0 3 4 5 62022/9/275(1466)計算直線的交點(diǎn)數(shù)問題描述：2022/9/296初步分析:我們知道:n條直線互不平行且無三線共點(diǎn)的最多交點(diǎn)數(shù)max=1+2+(n-1)=n(n-1)/2,但本題不這么簡單，因?yàn)閱栴}問的是：這些直線有多少種不同的交點(diǎn)數(shù)？2022/9/276初步分析:我們知道:2022/9/297思考2分鐘:如何解決?2022/9/277思考2分鐘:如何解決?2022/9/298然后，假設(shè)=n-1的情況都已經(jīng)知道分析思路 首先，容易列舉出N=1,2,3的情況：00，10，2，32022/9/278然后，假設(shè) 0+4*0+0=0；2、第四條

3、與其中兩條平行，交點(diǎn)數(shù)為0+(n-1)*1+0=3;3、第四條與其中一條平行，這兩條平行直線和另外兩點(diǎn)直線的交點(diǎn)數(shù)為(n-2)*2=4,而另外兩條直線既可能平行也可能相交，因此可能交點(diǎn)數(shù)為： 0+（n-2）*2+0=4 或者 0+(n-2)*2+1=5 4、 第四條直線不與任何一條直線平行，交點(diǎn)數(shù)為： 0+(n-3)*3+0=3 或0+ (n-3)*3+2=5 或0+ (n-3)*3+3=6即n=4時，有0個，3個，4個，5個，6個不同交點(diǎn)數(shù)。重點(diǎn)分析n的情況：2022/9/2710我們來分析加入第N條直線的情況(這里以2022/9/2911從上述n=4的分析過程中，我們發(fā)現(xiàn)：m條直線的交點(diǎn)方

4、案數(shù)=（m-r）條平行線與r條直線交叉的交點(diǎn)數(shù) + r條直線本身的交點(diǎn)方案=（m-r）*r+r條之間本身的交點(diǎn)方案數(shù)（0=r 109=10億）。試想一下：2022/9/2714這道題如果用枚舉法（暴力思想），在數(shù)2022/9/2915 拒絕暴力，倡導(dǎo)和諧2022/9/2715 拒絕暴力，倡導(dǎo)和諧2022/9/2916從頂點(diǎn)出發(fā)時到底向左走還是向右走應(yīng)取決于是從左走能取到最大值還是從右走能取到最大值，只要左右兩道路徑上的最大值求出來了才能作出決策。同樣，下一層的走向又要取決于再下一層上的最大值是否已經(jīng)求出才能決策。這樣一層一層推下去，直到倒數(shù)第二層時就非常明了。如數(shù)字2，只要選擇它下面較大值的結(jié)

5、點(diǎn)19前進(jìn)就可以了。所以實(shí)際求解時，可從底層開始，層層遞進(jìn)，最后得到最大值。結(jié)論：自頂向下的分析，自底向上的計算?？紤]一下：2022/9/2716從頂點(diǎn)出發(fā)時到底向左走還是向右走應(yīng)2022/9/2917二、思考題：最長有序子序列I012345678NumI1472583692022/9/2717二、思考題：最長有序子序列I012342022/9/2918解決方案：I012345678NumI147258369FI1232343452022/9/2718解決方案：I012345678Num2022/9/2919三、1160 FatMouses Speed Sample Input6008 130

6、0 6000 2100 500 2000 1000 4000 1100 3000 6000 2000 8000 1400 6000 1200 2000 1900 Sample Output4 4 5 9 72022/9/2719三、1160 FatMouses 2022/9/2920題目分析：設(shè)Micei.W表示第i只老鼠的重量，Micei.S表示第i只老鼠的速度。我們先對Mice進(jìn)行排序，以W為第一關(guān)鍵字，從小到大，S為第二關(guān)鍵字，從大到小。設(shè)fi為Micei至Micen最長的序列長度?？紤]某一個fi，則有： fi = max(fi, fj+1) (1=j Micej.W，Micei.S M

7、icej.S) 其中，初始條件為fi=1 (i=1, 2, ., n)。2022/9/2720題目分析：設(shè)Micei.W表示第i2022/9/2921Qestion:兩個問題有本質(zhì)區(qū)別嗎？2022/9/2721Qestion:兩個問題有本質(zhì)區(qū)別嗎2022/9/2922思考（期末考試題）：Super Jumping! Jumping!Juping! 2022/9/2722思考（期末考試題）：Super Ju解題思路？解題思路？2022/9/2924四、1159 Common SubsequenceSample Inputabcfbc abfcabprogramming contest abcd

8、mnp Sample Output 4 2 02022/9/2724四、1159 Common Sub2022/9/2925abcfbca111111b122222f122333c123334a123334b123344輔助空間變化示意圖2022/9/2725abcfbca111111b122222022/9/2926f(i,j)= 由于f(i,j)只和f(i-1,j-1), f(i-1,j)和f(i,j-1)有關(guān), 而在計算f(i,j)時, 只要選擇一個合適的順序, 就可以保證這三項都已經(jīng)計算出來了, 這樣就可以計算出f(i,j). 這樣一直推到f(len(a),len(b)就得到所要求的解

9、了.f(i-1,j-1)+1 (ai=bj)max(f(i-1,j),f(i,j-1) (ai!=bj) 子結(jié)構(gòu)特征：2022/9/2726f(i,j)= f(i-1,j-1)2022/9/2927思考：免費(fèi)餡餅 2022/9/2727思考：免費(fèi)餡餅 2022/9/2928如何解決？請發(fā)表見解 2022/9/2728如何解決？請發(fā)表見解 Any question?Any question?2022/9/2930理論小結(jié)2022/9/2730理論小結(jié)2022/9/2931如果各個子問題不是獨(dú)立的，不同的子問題的個數(shù)只是多項式量級，如果我們能夠保存已經(jīng)解決的子問題的答案，而在需要的時候再找出已求得

10、的答案，這樣就可以避免大量的重復(fù)計算。由此而來的基本思路是，用一個表記錄所有已解決的子問題的答案，不管該問題以后是否被用到，只要它被計算過，就將其結(jié)果填入表中。 一、動態(tài)規(guī)劃的基本思想 2022/9/2731如果各個子問題不是獨(dú)立的，不同的子問2022/9/2932二、動態(tài)規(guī)劃的基本步驟 動態(tài)規(guī)劃算法通常用于求解具有某種最優(yōu)性質(zhì)的問題。在這類問題中，可能會有許多可行解。每一個解都對應(yīng)于一個值，我們希望找到具有最優(yōu)值（最大值或最小值）的那個解。設(shè)計一個動態(tài)規(guī)劃算法，通?？梢园匆韵聨讉€步驟進(jìn)行： 2022/9/2732二、動態(tài)規(guī)劃的基本步驟 2022/9/2933（1）找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)

11、構(gòu)特征。（2）遞歸地定義最優(yōu)值。（3）以自底向上的方式計算出最優(yōu)值。（4）根據(jù)計算最優(yōu)值時得到的信息，構(gòu)造一個最優(yōu)解。其中（1）（3）步是動態(tài)規(guī)劃算法的基本步驟。在只需要求出最優(yōu)值的情形，步驟（4）可以省去。若需要求出問題的一個最優(yōu)解，則必須執(zhí)行步驟（4）。此時，在步驟（3）中計算最優(yōu)值時，通常需記錄更多的信息，以便在步驟（4）中，根據(jù)所記錄的信息，快速構(gòu)造出一個最優(yōu)解。基本步驟 2022/9/2733（1）找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特2022/9/2934三、動態(tài)規(guī)劃問題的特征 動態(tài)規(guī)劃算法的有效性依賴于問題本身所具有的兩個重要性質(zhì)：1、最優(yōu)子結(jié)構(gòu)：當(dāng)問題的最優(yōu)解包含了其子問題的最優(yōu)解時，稱該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。2、重疊子問題：在用遞歸算法自頂向下解問題時，每次產(chǎn)生的子問題并不總是新問題，有些子問題被反復(fù)計算多次。動態(tài)規(guī)劃算法正是利用了這種子問題的重疊性質(zhì)，對每一個子問題只解一次，而后將其解保存在一個表格中，在以后盡可能多地利用這些子問題的解。2022/9/2734三、動態(tài)規(guī)劃問題的特征 動態(tài)規(guī)劃算2022/9/2935課后任務(wù)：一、DIY在線作業(yè)(4):ACM程序設(shè)計在線作業(yè)（4） 動態(tài)規(guī)劃（第一部分） 二、常規(guī)練習(xí)（包含以上作業(yè)）100