工學(xué)動(dòng)態(tài)規(guī)劃ppt課件(編輯修改稿)
2024-11-30 20:37 本頁面
【文章內(nèi)容簡介】 /1 17 a b c f b c a 1 1 1 1 1 1 b 1 2 2 2 2 2 f 1 2 2 3 3 3 c 1 2 3 3 3 4 a 1 2 3 3 3 4 b 1 2 3 3 4 4 輔助空間變化示意圖 2021/12/1 18 f(i,j)= { ? 由于 f(i,j)只和 f(i1,j1), f(i1,j)和 f(i,j1)有關(guān) , 而在計(jì)算 f(i,j)時(shí) , 只要選擇一個(gè)合適的順序 , 就可以保證這三項(xiàng)都已經(jīng)計(jì)算出來了 , 這樣就可以計(jì)算出 f(i,j). 這樣一直推到 f(len(a),len(b))就得到所要求的解了 . f(i1,j1)+1 (a[i]==b[j]) max(f(i1,j),f(i,j1)) (a[i]!=b[j]) 子結(jié)構(gòu)特征： 2021/12/1 19 四、 經(jīng)典問題 ： 1421 搬寢室 Sample Input 2 1 1 3 Sample Output 4 2021/12/1 20 第一感覺： ? 根據(jù)題目的要求，每次提的兩個(gè)物品重量差越小越好，是不是每次提的物品一定是重量相鄰的物品呢？ ? 證明：假設(shè)四個(gè)從小到大的數(shù)： a、 b、 c、d，只需證明以下表達(dá)式成立即可： ? (ab)^2+(cd)^2 (ac)^2+(bd)^2 ? (ab)^2+(cd)^2 (ad)^2+(bc)^2 ? …… (略 ) 202
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1