acm基礎(chǔ)知識(shí)

1、ACM基礎(chǔ)知識(shí),2024/3/25,2,,動(dòng)態(tài)規(guī)劃 （Dynamic programming）,2024/3/25,3,,動(dòng)態(tài)規(guī)劃是一種將問題實(shí)例分解為更小的、相似的子問題，并存儲(chǔ)子問題的解而避免計(jì)算重復(fù)的子問題，以解決最優(yōu)化問題的算法策略基本要素最優(yōu)子結(jié)構(gòu)性質(zhì)子問題,2024/3/25,4,先熱身一下——,2024/3/25,5,一、數(shù)塔問題,,有形如下圖所示的數(shù)塔，從頂部出發(fā)，在每一結(jié)點(diǎn)可以選擇向左走或是向右走，一直走到底層

2、，要求找出一條路徑，使路徑上的值最大。,2024/3/25,6,用暴力的方法，可以嗎？,2024/3/25,7,這道題如果用枚舉法（暴力思想），在數(shù)塔層數(shù)稍大的情況下（如31），則需要列舉出的路徑條數(shù)將是一個(gè)非常龐大的數(shù)目（2^30= 1024^3 > 10^9=10億）。,試想一下：,解題思路？,2024/3/25,9,拒絕暴力，倡導(dǎo)和諧～,2024/3/25,10,理論小結(jié),2024/3/25,11,如果各個(gè)子問題不是獨(dú)立的，

3、不同的子問題的個(gè)數(shù)只是多項(xiàng)式量級(jí)，如果我們能夠保存已經(jīng)解決的子問題的答案，而在需要的時(shí)候再找出已求得的答案，這樣就可以避免大量的重復(fù)計(jì)算。由此而來的基本思路是，用一個(gè)表記錄所有已解決的子問題的答案，不管該問題以后是否被用到，只要它被計(jì)算過，就將其結(jié)果填入表中。,一、動(dòng)態(tài)規(guī)劃的基本思想,2024/3/25,12,二、動(dòng)態(tài)規(guī)劃的基本步驟,動(dòng)態(tài)規(guī)劃算法通常用于求解具有某種最優(yōu)性質(zhì)的問題。在這類問題中，可能會(huì)有許多可行解。每一個(gè)解都對(duì)應(yīng)于一個(gè)值

4、，我們希望找到具有最優(yōu)值（最大值或最小值）的那個(gè)解。設(shè)計(jì)一個(gè)動(dòng)態(tài)規(guī)劃算法，通?？梢园匆韵聨讉€(gè)步驟進(jìn)行：,2024/3/25,13,（1）找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征。（2）遞歸地定義最優(yōu)值。（3）以自底向上的方式計(jì)算出最優(yōu)值。（4）根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造一個(gè)最優(yōu)解。其中（1）－（3）步是動(dòng)態(tài)規(guī)劃算法的基本步驟。在只需要求出最優(yōu)值的情形，步驟（4）可以省去。若需要求出問題的一個(gè)最優(yōu)解，則必須執(zhí)行步驟（4）。此時(shí)，

5、在步驟（3）中計(jì)算最優(yōu)值時(shí)，通常需記錄更多的信息，以便在步驟（4）中，根據(jù)所記錄的信息，快速構(gòu)造出一個(gè)最優(yōu)解。,基本步驟,2024/3/25,14,三、動(dòng)態(tài)規(guī)劃問題的特征,動(dòng)態(tài)規(guī)劃算法的有效性依賴于問題本身所具有的兩個(gè)重要性質(zhì)：1、最優(yōu)子結(jié)構(gòu)：當(dāng)問題的最優(yōu)解包含了其子問題的最優(yōu)解時(shí)，稱該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。2、重疊子問題：在用遞歸算法自頂向下解問題時(shí)，每次產(chǎn)生的子問題并不總是新問題，有些子問題被反復(fù)計(jì)算多次。動(dòng)態(tài)規(guī)劃算法

6、正是利用了這種子問題的重疊性質(zhì)，對(duì)每一個(gè)子問題只解一次，而后將其解保存在一個(gè)表格中，在以后盡可能多地利用這些子問題的解。,2024/3/25,15,從頂點(diǎn)出發(fā)時(shí)到底向左走還是向右走應(yīng)取決于是從左走能取到最大值還是從右走能取到最大值，只要左右兩道路徑上的最大值求出來了才能作出決策。同樣，下一層的走向又要取決于再下一層上的最大值是否已經(jīng)求出才能決策。這樣一層一層推下去，直到倒數(shù)第二層時(shí)就非常明了。如數(shù)字2，只要選擇它下面較大值的

7、結(jié)點(diǎn)19前進(jìn)就可以了。所以實(shí)際求解時(shí)，可從底層開始，層層遞進(jìn)，最后得到最大值。結(jié)論：自頂向下的分析，自底向上的計(jì)算。,考慮一下：,2024/3/25,16,二、思考題：最長(zhǎng)有序子序列,2024/3/25,17,解決方案：,2024/3/25,18,最長(zhǎng)公共子序列,所以：結(jié)果為 3,a = { 1, 2, 4, 423, 5, 3};b = { 2, 2, 5, 5, 2, 1, 3};,2024/3/25,19,思考2分鐘:如

8、何解決?,,2024/3/25,20,動(dòng)態(tài)轉(zhuǎn)移方程,如果b[i] = a[j] map[i][j] = map[i-1][j-1]+1;否則 map[i][j] = max( map[i-1][j], map[i][j-1]),0 1 1 1 1 1 10 1 1 1 1 1 10 1 1 1 2 2 20 1 1 1 2 2 20 1 1 1 2 2 21 1 1 1 2 2 21 1 1 1 2 3 3,a =

9、{ 1, 2, 4, 423, 5, 3,0};b = { 2, 2, 5, 5, 2, 1, 3};,2024/3/25,21,,如果b[i] == a[j] m[j] = m[j-1] +1;否則 m[j] = max( m[j], m[j-1]);,2024/3/25,22,迷宮,,,入口,出口,2024/3/25,23,如何解決？,請(qǐng)發(fā)表見解 ?,2024/3/25,24,斐波那鍥數(shù)列,f[n] = f[n-1]+f