程序類競賽中的動(dòng)態(tài)規(guī)劃算法探討

盧揚(yáng)城，毛玉萃，關(guān)澤群

摘要：動(dòng)態(tài)規(guī)劃問題在各類程序設(shè)計(jì)競賽中常常出現(xiàn)。該文首先簡單介紹了動(dòng)態(tài)規(guī)劃算法，闡述了利用動(dòng)態(tài)規(guī)劃解決實(shí)際問題的流程，并通過實(shí)例進(jìn)一步探討了線性動(dòng)態(tài)規(guī)劃、區(qū)間動(dòng)態(tài)規(guī)劃、樹形動(dòng)態(tài)規(guī)劃、背包動(dòng)態(tài)規(guī)劃以及狀態(tài)壓縮動(dòng)態(tài)規(guī)劃算法問題，簡單介紹了動(dòng)態(tài)規(guī)劃算法思想在其他經(jīng)典算法中的應(yīng)用，最后進(jìn)行了簡單總結(jié)。

關(guān)鍵詞：動(dòng)態(tài)規(guī)劃;程序類競賽;實(shí)例;

中圖分類號(hào)：TP311.52? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2021）21-0093-04

開放科學(xué)（資源服務(wù)）標(biāo)識(shí)碼（OSID）：

1 動(dòng)態(tài)規(guī)劃算法的概述[1-2]

動(dòng)態(tài)規(guī)劃算法在是許多算法的理論基礎(chǔ)，在傳統(tǒng)決策性問題、圖論問題、字符串問題等問題中都有涉及，因此是程序設(shè)計(jì)類競賽考察的重點(diǎn)。

動(dòng)態(tài)規(guī)劃算法的核心是利用記憶化處理方式、依托貪心思想、記錄歷史數(shù)據(jù)來達(dá)到優(yōu)化時(shí)間復(fù)雜度的目的，簡而言之就是“用空間換時(shí)間”;在求解過程中采用分治思想，對(duì)問題分階段進(jìn)行決策。圖1所示為動(dòng)態(tài)規(guī)劃的分階段決策。

動(dòng)態(tài)規(guī)劃算法需要滿足以下幾個(gè)特征：

1.1 無后效性

無后效性是指當(dāng)前狀態(tài)一旦確定，則之后的所有狀態(tài)與之前的情況無關(guān)，僅僅與當(dāng)前狀態(tài)的決策有關(guān)，因此要著重研究當(dāng)前狀態(tài)。

1.2 最優(yōu)子結(jié)構(gòu)

動(dòng)態(tài)規(guī)劃算法經(jīng)常解決的是最值性問題。最優(yōu)化子結(jié)構(gòu)保證各階段求解的方案決策具有類似的最值結(jié)構(gòu)，即決策滿足貪心思想下的解也一定是子解的最優(yōu)解。

1.3 子問題重疊

即所分解得到的子問題之間不是相互獨(dú)立的，在之后的階段還可能被多次使用到。這一點(diǎn)不是動(dòng)態(tài)規(guī)劃算法適用的必要條件，但是如果沒有這個(gè)特征，動(dòng)態(tài)規(guī)劃算法便不具有時(shí)間上的優(yōu)勢(shì)。

動(dòng)態(tài)規(guī)劃算法中狀態(tài)定義和狀態(tài)轉(zhuǎn)移方程設(shè)計(jì)是核心。狀態(tài)定義是解決動(dòng)態(tài)規(guī)劃問題的關(guān)鍵，把問題分成幾個(gè)不同的情況對(duì)這些情況的抽象描述即是狀態(tài)定義。狀態(tài)轉(zhuǎn)移方程是決策問題中的指南針，設(shè)計(jì)正確的狀態(tài)轉(zhuǎn)移方程是求解問題的重中之重，圖2表示狀態(tài)轉(zhuǎn)移方程的作用。各階段狀態(tài)由歷史狀態(tài)轉(zhuǎn)移而來，從眾多的歷史狀態(tài)中選擇哪一個(gè)就是狀態(tài)轉(zhuǎn)移方程要解決的任務(wù)。

2 動(dòng)態(tài)規(guī)劃求解問題的流程[1-4]

動(dòng)態(tài)規(guī)劃算法由其分階段性和依托性，可將其分為正向遞推和反向遞推，利用分治思想從小問題逐漸遞推到大問題，注意遞推過程的邏輯性，觀察不同狀態(tài)間的特征及其之間的內(nèi)在邏輯、不同點(diǎn)和相同點(diǎn)來得出初步遞推公式。正向遞推通常從“當(dāng)前狀態(tài)可以得到哪些狀態(tài)”的大致思路思考，反向遞推通常由“當(dāng)前狀態(tài)可以由哪些狀態(tài)得到”的大致思路來思考。捋順遞推過程是解決動(dòng)態(tài)規(guī)劃問題十分關(guān)鍵的一步，確定了遞推關(guān)系才能解決整個(gè)問題，遞推關(guān)系的體現(xiàn)就是狀態(tài)轉(zhuǎn)移方程。動(dòng)態(tài)規(guī)劃求解問題的過程如圖3所示。

首先確定狀態(tài)就是根據(jù)問題描述中的信息整理出相關(guān)的量，這些量必須是相互獨(dú)立的，也就是說在邏輯上問題的狀態(tài)由這些量構(gòu)成，缺少任意一個(gè)量狀態(tài)問題的表示就不明確，在確定狀態(tài)量時(shí)必須兼顧內(nèi)存空間的要求，不能一味地追求細(xì)致刻畫狀態(tài)，而造成冗余狀態(tài)的表示和無用信息的附加，這在動(dòng)態(tài)規(guī)劃算法優(yōu)化部分著重介紹;其次確定基本量、依托量?；玖客ǔＲ灶}干給定的信息為主，在不需要推導(dǎo)的情況下就可以得到。依托量通常是抽象量，指的是我們對(duì)答案的構(gòu)成描述，依托量的某個(gè)狀態(tài)的全集就是最終的答案。再次根據(jù)問題描述中給定信息尋找不同量之間的遞推關(guān)系，可以運(yùn)用正向遞推的方式也可以運(yùn)用反向遞推的方式，通常情況下較難的題涉及的遞推思想常常與反向遞推有關(guān)，確定了遞推公式，接下來可以描述出狀態(tài)轉(zhuǎn)移方程的大致輪廓。許多涉及數(shù)組間遞推的動(dòng)態(tài)規(guī)劃問題中，常見到以數(shù)組下標(biāo)為基本量，以原數(shù)組數(shù)值為依托量來確定其遞推關(guān)系。描述了狀態(tài)轉(zhuǎn)移方程之后要確定狀態(tài)的初始情況，即確定初態(tài)，初態(tài)必須合乎狀態(tài)轉(zhuǎn)移方程的邏輯要求，初態(tài)的確定對(duì)算法來說有著舉足輕重的作用。最后要確定哪些狀態(tài)集合包含答案，通過遍歷該集合得到答案。

3 各類動(dòng)態(tài)規(guī)劃的解題思路和應(yīng)用舉例

動(dòng)態(tài)規(guī)劃問題按其狀態(tài)轉(zhuǎn)移方程的形態(tài)和存儲(chǔ)方式，可以劃分為線性動(dòng)態(tài)規(guī)劃、區(qū)間動(dòng)態(tài)規(guī)劃問題、樹形動(dòng)態(tài)規(guī)劃問題、背包動(dòng)態(tài)規(guī)劃問題和狀態(tài)壓縮動(dòng)態(tài)規(guī)劃[1，3-5]。

3.1 線性動(dòng)態(tài)規(guī)劃

線性動(dòng)態(tài)規(guī)劃包含了動(dòng)態(tài)規(guī)劃的最基本的思想，是在線性結(jié)構(gòu)上進(jìn)行狀態(tài)轉(zhuǎn)移的，是最簡單的動(dòng)態(tài)規(guī)劃，該類動(dòng)態(tài)規(guī)劃空間復(fù)雜度一般為O（n），問題大多較為簡單。其他復(fù)雜類型的動(dòng)態(tài)規(guī)劃都是在它的基礎(chǔ)上增加優(yōu)化算法、增加狀態(tài)維度和在各種抽象數(shù)據(jù)結(jié)構(gòu)上等的模型。

例1（原題見參考文獻(xiàn)[6]）問題簡述：一個(gè)游戲由一個(gè)棋盤和一些棋子組成，所有的棋子都用一個(gè)正整數(shù)或“開始”或“結(jié)束”來標(biāo)記。玩家從起點(diǎn)開始，最后必須跳到終點(diǎn)。在跳躍過程中，玩家將訪問路徑中的棋子，但每個(gè)人必須從一個(gè)棋子跳到另一個(gè)絕對(duì)大的棋子（假設(shè)起點(diǎn)是最小值，終點(diǎn)是最大值）。所有玩家都不能倒退。一跳可以從一個(gè)棋子跳到下一個(gè)棋子，也可以跨越多個(gè)棋子，甚至可以從起點(diǎn)直達(dá)終點(diǎn)。一個(gè)球員是贏家，當(dāng)且僅當(dāng)他能得到一個(gè)更大的分?jǐn)?shù)，根據(jù)他的跳躍解決方案。一個(gè)玩家的分?jǐn)?shù)來自他跳躍路徑中棋子上的值的總和，求最大分?jǐn)?shù)是多少。

這題是一道最長上升子序列的模板題。

子序列與子數(shù)組是區(qū)別。子序列指的是由原序列刪除若干元素后，剩下的元素由相對(duì)位置不變的方式得到的一個(gè)有序集合。子數(shù)組是原序列上一段連續(xù)的有序集合。

此問題可以說是動(dòng)態(tài)規(guī)劃入門的經(jīng)典問題并且是一個(gè)線性動(dòng)態(tài)規(guī)劃。假設(shè)數(shù)組為sl，設(shè)到sl[i]的最長長上升子序列的長度為dp[i]，最初dp[i]=1，即到sl[i] 的最長上升子序列的長度初始值1，即數(shù)組中的每一個(gè)數(shù)都是包含自身的一個(gè)數(shù)的最長上升子序列 ?？紤]狀態(tài)轉(zhuǎn)移方程的確定，在計(jì)算dp[i]的值之前，就已經(jīng)計(jì)算出sl[i]前面的最長上升子序列的長度。當(dāng)數(shù)sl[i]大于往前遍歷到的數(shù)sl[j]時(shí)（j