李建
摘 要:技術(shù)科目作為浙江省新高考科目以來,算法加試部分難度不斷提高。近幾年的考題對計(jì)數(shù)思想的考查,更標(biāo)志著程序填空題的難度從代碼層面到思維深度的跨越。文章作者將結(jié)合思維程度的深入,逐步給出數(shù)個(gè)經(jīng)典動(dòng)態(tài)規(guī)劃問題的思考過程,并提出一種“加一維”的思考方法,切實(shí)有效提高學(xué)生解決動(dòng)態(tài)規(guī)劃問題的能力。
關(guān)鍵詞:動(dòng)態(tài)規(guī)劃;狀態(tài)定義;狀態(tài)轉(zhuǎn)移;加一維
中圖分類號:O221.3 文獻(xiàn)標(biāo)識(shí)碼:A 收稿日期:2019-04-07 文章編號:1674-120X(2019)24-0117-02
很多教師錯(cuò)誤地認(rèn)為動(dòng)態(tài)規(guī)劃問題就是背包問題,甚至有教師因?yàn)樵搯栴}太過抽象,“簡單粗暴”地讓學(xué)生死記背包模型代碼,顯然這種教學(xué)方法是非常不可取的。
下面筆者逐步給出數(shù)個(gè)經(jīng)典動(dòng)態(tài)規(guī)劃問題的解題步驟,建立概念之間的內(nèi)在聯(lián)系,讓學(xué)生了解動(dòng)態(tài)規(guī)劃算法的本質(zhì),并提出“加一維”,切實(shí)有效提高學(xué)生解決問題的能力。
一、動(dòng)態(tài)規(guī)劃算法基本原理
在信息學(xué)競賽中,第一次考查動(dòng)態(tài)規(guī)劃是在IOI1994(國際信息學(xué)競賽)中的“數(shù)塔問題”,雖然當(dāng)時(shí)全世界信息學(xué)頂尖選手的此題得分率極低,但是現(xiàn)在已經(jīng)作為DP算法的入門題出現(xiàn)。其模型比較直觀,有助于我們理解動(dòng)態(tài)規(guī)劃算法中的相關(guān)概念和性質(zhì)。很多教師在講授動(dòng)態(tài)規(guī)劃時(shí),先羅列相關(guān)生澀的概念,很多學(xué)生對此無法真正理解。下面我們從一個(gè)相對直觀的問題出發(fā),一步一步引導(dǎo)學(xué)生主動(dòng)思考,在解決問題的過程中,學(xué)生可以逐漸理解問題的本質(zhì)。
問題一:數(shù)塔問題。有一些數(shù)字排成數(shù)塔的形狀,其中第一層有一個(gè)數(shù)字,第二層有兩個(gè)數(shù)字……第n層有n個(gè)數(shù)字?,F(xiàn)在要從第一層走到第n層,每次只能選擇左下方或者右下方的數(shù)字,問:“最后將路徑上所有數(shù)字相加后得到的和最大是多少?”
教師引導(dǎo)思考過程:
(1)從起點(diǎn)到第一行第一列的答案是固定的。
(2)在第一步驟基礎(chǔ)上,從起點(diǎn)到第二行的答案也是固定的。
(3)在第三行時(shí),7有兩種選擇,顯然選擇累積更大的8才是最優(yōu)的。若將f[i][j]定義為從第一行第一列到第i行第j列的路徑上的數(shù)字和的最大值,則到數(shù)字7的遞推式為:f[3][2] = max(f[2][1] , f[2][2])+7。
(4)可得出一般遞推式為f[i][j]=max(f[i-1][j-1],f[i-1][j])+a[i][j],我們只需要推到第n行,就可以得到ans=max(f[n][1…n])。
解法提煉:
(1)狀態(tài)定義:f[i][j]定義從第一行第一列到第i行第j列的路徑上的數(shù)字和的最大值。
(2)所求:max(f[n][1…n])。
(3)狀態(tài)轉(zhuǎn)移:f[i][j]=max(f[i-1][j-1],f[i-1][j])+a[i][j]。
正確性分析:
(1)前面推導(dǎo)的結(jié)果不會(huì)隨著后幾行得到的結(jié)果而改變——無后效性。
(2)局部最優(yōu)可以保證全局最優(yōu)——最優(yōu)子結(jié)構(gòu)。
這兩個(gè)性質(zhì)也是動(dòng)態(tài)規(guī)劃算法解決問題的先決條件。
二、動(dòng)態(tài)規(guī)劃的狀態(tài)定義
問題二:最長上升子序列問題。給定一個(gè)長度為n的數(shù)字序列,求最長的上升子序列長度。如3,1,2,6,4,5的最長上升子序列為1,2,4,5,故答案為4。
在問題一的基礎(chǔ)上,很容易想到如下解法。
(1)狀態(tài)定義:f[i]定義為到第i個(gè)數(shù)字為止,能獲得最長子序列長度。
(2)所求:f[n]。
(3)狀態(tài)轉(zhuǎn)移:顯然此時(shí)很難尋找到f[i]關(guān)于f[1…i-1]的遞推關(guān)系。
無法找到遞推關(guān)系是由于遞推時(shí)的大小關(guān)系需要第i個(gè)數(shù)與前面某個(gè)確定的數(shù)進(jìn)行比較,而原有的狀態(tài)定義無法得知哪些數(shù)字被選中,故無法直接進(jìn)行比較,帶著這個(gè)問題,容易想到新的解法。
(1)狀態(tài)定義:f[i]定義為到第i個(gè)數(shù)字為止,且第i個(gè)數(shù)必須為改子序列的最后一個(gè)數(shù)字時(shí),所獲得的最長子序列的長度。
(2)所求:max(f[1…n])。