1. 項目概述從開源學習到動態規劃的核心最近在Datawhale的開源學習社區里看到不少朋友在啃數學建模這塊硬骨頭尤其是動態規劃這個聽起來就有點“動態”又有點“規劃”的算法。很多人一聽到這個名字第一反應可能是“這玩意兒是不是特別難是不是只有搞ACM競賽的大神才用得上”其實完全不是。動態規劃是數學建模和算法設計中一個極其強大且實用的工具它解決的是那些可以分解為重疊子問題的最優化問題。簡單來說就是當你面對一個復雜的大問題時動態規劃教你如何聰明地“記住”已經解決過的小問題的答案避免重復計算從而高效地找到全局最優解。Datawhale這個開源學習項目把動態規劃作為數學建模學習路徑上的一環我覺得特別對路。無論是準備國賽、美賽還是亞太杯無論是解決資源分配、路徑優化還是生產調度問題動態規劃的身影都無處不在。比如經典的“背包問題”給你一個背包一些物品各有重量和價值如何裝包使總價值最大或者“最短路徑問題”其核心思想都可以用動態規劃來優雅地建模和求解。這個學習內容的目標就是幫大家剝開動態規劃那層看似抽象的外衣理解其“狀態定義”、“狀態轉移方程”和“最優子結構”這三個核心思想并能夠動手用代碼比如Python實現它最終應用到自己的建模論文中。無論你是剛開始接觸建模的小白還是想鞏固算法基礎的老手掌握動態規劃都能讓你在解決一類最優化問題時思路更清晰方案更有力。2. 動態規劃的核心思想與“靈魂三問”要學好動態規劃死記硬背幾個經典模型是沒用的關鍵是要吃透它的核心思想。我自己剛學的時候也繞了不少彎路后來發現只要在遇到一個問題時能成功回答下面三個問題動態規劃的框架就自然浮現出來了。我把這三個問題稱為動態規劃的“靈魂三問”。2.1 第一問問題的“狀態”是什么“狀態”是動態規劃里最核心的概念。你可以把它理解為描述問題在某個“階段”或“局面”下的一組關鍵信息。這組信息必須足夠精簡能夠唯一確定當前的局面并且能通過它推導出后續的局面。舉個例子在經典的“爬樓梯”問題中假設你每次可以爬1級或2級臺階爬到第n級有多少種方法。這里唯一的、關鍵的變量就是你當前所處的臺階級數i。dp[i]就可以定義為“爬到第i級臺階的方法總數”。這個i就是我們的狀態。它足夠簡單并且知道了i我們就能去思考怎么從i-1或i-2轉移過來。而在“0-1背包問題”中狀態就需要兩個維度來描述當前考慮到第幾個物品i以及當前背包的剩余容量j。dp[i][j]就表示“考慮前i個物品在背包容量為j的情況下可以裝下的最大價值”。你看這兩個信息i和j一組合就完全刻畫了“考慮前i個物品容量為j”這個子問題。實操心得定義狀態時一個常見的坑是“狀態定義得過于復雜或冗余”。好的狀態應該是“最小信息集”。如果你發現定義的狀態無法清晰地寫出轉移方程或者存在后效性當前決策會影響之前的狀態那很可能就是狀態定義出了問題。多從問題本身出發問自己“要描述當前這一步最少需要知道哪幾個變量”2.2 第二問狀態之間如何“轉移”定義了狀態下一步就是找出狀態與狀態之間的關系也就是狀態轉移方程。這是動態規劃的“發動機”。它描述了如何從一個或多個已知的、規模較小的子問題的解狀態推導出當前這個規模較大的問題的解。繼續看“爬樓梯”要爬到第i級你最后一步只能是從第i-1級爬1級上來或者從第i-2級爬2級上來。既然這兩種方式是“最后一步”的不同選擇那么爬到第i級的總方法數自然就是爬到第i-1級的方法數加上爬到第i-2級的方法數。所以狀態轉移方程就是dp[i] dp[i-1] dp[i-2]。 這里dp[i-1]和dp[i-2]就是更小規模的子問題的解。對于“0-1背包”狀態轉移就需要一點決策思維了。面對第i個物品重量w[i]價值v[i]我們有兩種選擇不裝那么最大價值就等于考慮前i-1個物品、容量為j時的最大價值即dp[i-1][j]。裝前提是背包容量j能裝下它即j w[i]那么最大價值就等于“第i個物品的價值v[i]”加上“考慮前i-1個物品、剩余容量為j - w[i]時的最大價值”即v[i] dp[i-1][j - w[i]]。我們的目標是價值最大所以在這兩種選擇中取最大值dp[i][j] max(dp[i-1][j], v[i] dp[i-1][j - w[i]])當j w[i]時。注意事項寫轉移方程時務必考慮邊界條件。比如上面的背包問題當j w[i]時根本裝不下那么dp[i][j]就只能等于dp[i-1][j]。這些邊界處理是代碼正確性的保障也是建模時邏輯嚴謹性的體現。2.3 第三問問題的“邊界”在哪里邊界就是那些最小、最初、不需要再分解的子問題的解。它們是整個動態規劃遞推過程的起點就像蓋房子的地基。對于“爬樓梯”dp[1] 1爬到第1級只有1種方法爬1級dp[2] 2爬到第2級有2種方法11 或 直接爬2級。有些題目為了編碼方便也會定義dp[0] 1“爬到”第0級算1種方法一種虛擬的起點。對于“0-1背包”當沒有物品可選時i0無論背包容量j是多少最大價值都是0。所以我們的邊界是dp[0][j] 0for allj。只有明確了邊界我們的遞推過程才能從這些已知點開始一步步“滾雪球”似地計算出最終目標狀態dp[n]或dp[n][C]的值。把這“靈魂三問”的答案想清楚一個動態規劃問題的解題框架就基本搭建完成了。剩下的就是用代碼把這個框架實現出來。3. 經典模型拆解從理論到代碼實現理解了思想我們來看兩個最經典、在數學建模中也最高頻出現的動態規劃模型。我會給出詳細的思路分析和可以直接“抄作業”的Python代碼模板。3.1 模型一0-1背包問題——資源分配的基石0-1背包問題幾乎是所有資源限制類優化問題的母題。它的場景是有N件物品和一個容量為C的背包。第i件物品的重量是w[i]價值是v[i]。每件物品只能選擇“放”或“不放”0或1。求解將哪些物品裝入背包可使總價值最大。狀態定義dp[i][j]表示考慮前i件物品在背包容量為j的情況下能獲得的最大價值。狀態轉移方程如果 j w[i]: // 當前背包容量裝不下第i件物品 dp[i][j] dp[i-1][j] // 只能選擇不裝 否則: // 能裝下需要在“裝”和“不裝”之間決策 dp[i][j] max(dp[i-1][j], // 選擇不裝 v[i] dp[i-1][j - w[i]]) // 選擇裝邊界條件dp[0][j] 0(0件物品價值為0)。代碼實現Pythondef knapsack_01(N, C, w, v): 0-1背包問題動態規劃解法 :param N: 物品數量 :param C: 背包容量 :param w: 物品重量列表長度N :param v: 物品價值列表長度N :return: 能獲得的最大價值 # 初始化dp數組多一行一列是為了方便處理邊界i0和j0 dp [[0] * (C 1) for _ in range(N 1)] # 動態規劃填表過程 for i in range(1, N 1): # 遍歷物品 for j in range(1, C 1): # 遍歷背包容量 if j w[i-1]: # 注意w和v的索引從0開始所以用i-1 # 裝不下繼承上一個物品決策的結果 dp[i][j] dp[i-1][j] else: # 裝得下決策不裝 或 裝 dp[i][j] max(dp[i-1][j], v[i-1] dp[i-1][j - w[i-1]]) # 最終答案考慮所有N個物品容量為C時的最大價值 return dp[N][C] # 示例 N 4 C 5 w [2, 1, 3, 2] v [12, 10, 20, 15] max_value knapsack_01(N, C, w, v) print(f最大價值為: {max_value}) # 輸出最大價值為: 37空間優化滾動數組 上面的代碼空間復雜度是 O(N*C)。觀察狀態轉移方程我們發現dp[i][j]只依賴于dp[i-1][...]即上一行的數據。因此我們可以只用一維數組dp[j]來迭代更新但需要逆序遍歷背包容量j以確保在計算dp[j]時dp[j - w[i-1]]還是上一輪i-1時的值沒有被本輪覆蓋。def knapsack_01_optimized(N, C, w, v): dp [0] * (C 1) for i in range(N): # 必須逆序遍歷容量j for j in range(C, w[i] - 1, -1): dp[j] max(dp[j], v[i] dp[j - w[i]]) return dp[C]這個優化技巧非常重要能極大節省內存尤其是在容量C很大時。3.2 模型二最長上升子序列LIS——序列型問題的代表最長上升子序列問題描述給定一個無序的整數序列找到其中最長的、元素嚴格遞增的子序列的長度。注意子序列不要求連續。例如序列[10, 9, 2, 5, 3, 7, 101, 18]的最長上升子序列之一是[2, 3, 7, 101]長度為4。這個問題是序列型動態規劃的經典在建模中可用于分析趨勢、尋找最優增長路徑等。狀態定義dp[i]表示以第i個數字結尾的最長上升子序列的長度。注意這個定義強制了子序列的結尾是nums[i]。狀態轉移方程 為了求dp[i]我們需要看i之前的所有位置j(0 j i)。如果nums[i] nums[j]說明nums[i]可以接在nums[j]結尾的子序列后面形成一個更長的上升子序列。因此dp[i] max(dp[j]) 1對于所有滿足0 j i且nums[j] nums[i]的j。 如果不存在這樣的j即nums[i]比前面所有數都小那么dp[i] 1它自己構成一個長度為1的子序列。邊界條件每個位置至少可以以自己結尾所以初始時每個dp[i]都可以設為1。代碼實現Pythondef length_of_lis(nums): 計算最長上升子序列的長度 :param nums: 整數列表 :return: 最長上升子序列的長度 if not nums: return 0 n len(nums) dp [1] * n # 初始化dp數組每個位置至少長度為1 max_length 1 for i in range(1, n): # 遍歷每個位置i for j in range(i): # 遍歷i之前的所有位置j if nums[i] nums[j]: # 如果nums[i]能接在nums[j]后面則嘗試更新dp[i] dp[i] max(dp[i], dp[j] 1) # 更新全局最大長度 max_length max(max_length, dp[i]) return max_length # 示例 nums [10, 9, 2, 5, 3, 7, 101, 18] result length_of_lis(nums) print(f最長上升子序列長度為: {result}) # 輸出4算法優化貪心二分查找 上述解法時間復雜度為 O(n2)對于較長的序列可能較慢。存在一種更優的 O(n log n) 解法其思路是維護一個數組tails其中tails[k]存儲長度為k1的上升子序列的最小可能末尾元素。這個數組本身是遞增的我們可以用二分查找來更新它。這個優化版本在建模競賽中如果遇到數據規模大的情況會非常有用體現了算法優化的價值。def length_of_lis_optimized(nums): tails [] # tails[k] 表示長度為k1的LIS的最小末尾元素 for num in nums: # 在tails中尋找第一個大于等于num的位置 left, right 0, len(tails) while left right: mid (left right) // 2 if tails[mid] num: left mid 1 else: right mid # 如果left等于tails長度說明num比所有末尾都大可以延長LIS if left len(tails): tails.append(num) else: # 否則用num替換掉那個第一個大于等于它的元素保持tails的“最小末尾”性質 tails[left] num # tails的長度就是LIS的長度 return len(tails)4. 數學建模中的動態規劃實戰場景在數學建模競賽中動態規劃絕不僅僅是解兩道算法題。它是一把解決多階段決策優化問題的利器。下面我結合幾個常見的建模題型講講動態規劃是怎么融入進去的。4.1 場景一生產計劃與資源調度這類問題通常涉及在多個時間周期內決定生產量、庫存量、資源分配量等以最小化總成本或最大化總利潤。問題通常具有時間上的階段性并且當前決策會影響未來的狀態如庫存這正好符合動態規劃“多階段決策”和“狀態轉移”的特征。建模思路定義階段通常將每個時間周期如天、周、月作為一個階段t。定義狀態狀態需要能描述在階段t開始時的局面。關鍵狀態變量往往是庫存量I_t。有時還包括其他資源狀態。定義決策變量在每個階段t決策通常是生產量x_t。建立狀態轉移方程描述狀態如何隨決策變化。例如下個階段的庫存 當前庫存 生產量 - 本期需求量。即I_{t1} I_t x_t - d_td_t為t階段的需求。定義成本/收益函數每個階段的成本可能包括生產成本與x_t相關、庫存持有成本與I_t相關。構建動態規劃遞歸式設F_t(I_t)表示從階段t開始初始庫存為I_t到計劃期末的最小總成本。那么遞歸關系通常是F_t(I_t) min_{x_t} { cost_t(x_t, I_t) F_{t1}(I_{t1}) }其中I_{t1}由狀態轉移方程給出cost_t是階段t的成本F_{t1}是后續子問題的最優成本。從最后一個階段倒推回來最終F_1(I_1)就是全局最優解。實操要點離散化庫存、生產量可能是連續變量為了用動態規劃求解通常需要將其離散化為有限的幾個水平這會引入近似需要在精度和計算復雜度之間權衡。維度災難如果狀態變量不止一個比如多產品、多資源狀態空間會指數級增長導致計算不可行。這時需要考慮問題是否有特殊結構如可分離性或者使用近似動態規劃方法。4.2 場景二投資組合優化在一定的風險偏好下如何將資金分配到不同的資產如股票、債券以在一定時期內最大化預期收益或最小化風險這是一個典型的多階段隨機決策問題可以用動態規劃來建模。建模思路簡化版階段將投資期劃分為多個時段如每年為一個階段。狀態狀態是t時期初的財富總量W_t以及可能的市場狀態如牛市、熊市。決策在每個階段t決策是如何分配財富到n種資產上即一個投資比例向量u_t (u_{t1}, ..., u_{tn})滿足∑ u_{ti} 1。狀態轉移財富的演化是隨機的取決于資產收益率r_t隨機向量。W_{t1} W_t * (1 u_t^T * r_t)。目標函數通常是最終財富W_T的期望效用最大化即max E[U(W_T)]其中U(·)是效用函數反映風險偏好。動態規劃方程貝爾曼方程定義值函數V_t(W_t)為從時期t、財富W_t開始到期末所能獲得的最大期望效用。V_t(W_t) max_{u_t} E[ V_{t1}( W_t * (1 u_t^T * r_t) ) ]從期末T開始V_T(W_T) U(W_T)逆向遞歸求解。注意事項隨機性這是隨機動態規劃。期望E[·]需要對資產收益率的隨機分布求積分或求和計算復雜。在實際建模中常采用離散化收益率場景情景樹或蒙特卡洛模擬來近似處理。連續狀態財富W_t是連續變量直接求解困難。常用方法是將其離散化到網格點上或者利用函數近似如多項式近似來表示值函數V_t(W)。4.3 場景三路徑規劃與網絡流問題在交通、物流建模中經常需要找最短路徑、最少時間路徑、或者最大可靠路徑。當圖中存在負權邊、或者問題有額外約束如時間窗、資源限制時簡單的Dijkstra算法可能不再適用而動態規劃提供了更通用的框架。例如帶時間窗的最短路徑問題。車輛從起點出發要在每個客戶點規定的服務時間窗內到達求滿足所有時間窗約束的最短行駛路徑。建模思路階段可以按訪問的客戶數量來劃分階段或者按時間片來劃分。狀態狀態可以定義為(當前所在位置, 當前時間, 已訪問過的客戶集合)。這里“已訪問過的客戶集合”可能用位掩碼表示用于處理組合爆炸。決策從當前狀態決策下一個前往哪個未訪問且能在其時間窗內到達的客戶點。狀態轉移轉移到新狀態更新位置、時間加上行駛時間和可能的等待時間并將新客戶加入已訪問集合。動態規劃遞歸定義dp[loc][t][mask]為在位置loc、時間t、已訪問集合為mask的狀態下的最小成本或是否可行。從起點狀態開始遞推或記憶化搜索。挑戰與技巧狀態空間巨大(位置×時間×客戶集合)的狀態數可能非常龐大。這屬于**旅行商問題TSP**的變種是NP-hard的。對于小規模問題客戶數20動態規劃狀態壓縮DP是精確求解的有效方法。對于大規模問題則需要結合啟發式算法或列生成等高級優化方法。建模中的取舍在數學建模比賽中面對這類復雜問題往往需要對模型進行合理簡化例如放松某些約束、聚合節點、或者設計高效的啟發式規則在可接受的時間內得到一個滿意解而不是執著于精確最優解。5. 從模型到代碼一個完整的建模案例實現為了讓大家更直觀地感受動態規劃在建模中的應用我們來看一個簡化版的生產庫存管理問題并用Python完整實現。問題描述 某工廠需要制定一個為期4周的生產計劃。已知每周的需求量d [2, 3, 2, 4]單位千件。每周的生產能力上限為6千件。每千件產品的生產成本是3千元。如果當周生產了產品但沒有立刻滿足需求就需要進入庫存每周每千件的庫存持有成本是0.5千元。期初庫存為1千件且希望期末庫存為0。目標是制定一個生產計劃每周生產多少使得總成本生產成本庫存持有成本最小。動態規劃建模階段t 1, 2, 3, 4共4周。狀態I_t表示第t周期初的庫存量。根據生產能力、需求量和期初庫存我們可以確定狀態I_t的可能取值范圍。決策x_t表示第t周的生產量。約束0 x_t 6生產能力且必須滿足I_t x_t d_t生產加庫存要能滿足當期需求。狀態轉移I_{t1} I_t x_t - d_t。且I_{t1} 0。成本第t周的成本 生產成本3 * x_t 庫存持有成本0.5 * I_t。注意庫存成本通常按周期初或期末庫存計算這里我們按周期初庫存計算即為一周內持有的平均庫存近似。目標最小化總成本。邊界條件I_1 1期初庫存I_5 0期末庫存要求。由于狀態和決策變量都是離散的我們可以假設生產量和庫存量都以千件為單位是整數我們可以用動態規劃表格法來求解。Python代碼實現def production_planning(): # 問題參數 d [2, 3, 2, 4] # 每周需求 weeks len(d) max_production 6 prod_cost_per_unit 3 holding_cost_per_unit 0.5 initial_inv 1 final_inv 0 # 確定狀態庫存的可能范圍。為簡化我們估計一個范圍。 # 最大庫存不會超過 (max_production - min(d)) * t 的累積這里簡單設一個上界。 max_inv 10 # 假設庫存上限為10 # 初始化DP表dp[t][i] 表示第t周初庫存為i時從第t周到結束的最小總成本 # 我們用一個大數inf表示不可行狀態 INF float(inf) dp [[INF] * (max_inv 1) for _ in range(weeks 2)] # 多一周用于邊界 decision [[None] * (max_inv 1) for _ in range(weeks 2)] # 記錄最優決策 # 邊界條件第5周初即第4周末庫存必須為0 for inv in range(max_inv 1): if inv final_inv: dp[weeks 1][inv] 0 # 從第5周開始成本為0 else: dp[weeks 1][inv] INF # 不符合期末庫存要求不可行 # 逆序動態規劃從最后一周往前推 for t in range(weeks, 0, -1): # t從4到1 for inv in range(max_inv 1): # 當前周期初庫存inv min_cost INF best_x None # 枚舉本周可能的生產量x for x in range(max_production 1): # 檢查可行性生產后必須滿足當期需求 if inv x d[t-1]: continue # 計算下一周期初庫存 next_inv inv x - d[t-1] if next_inv max_inv or next_inv 0: continue # 超出我們設定的庫存范圍或為負實際上不會為負因上面檢查了需求 # 計算本周成本 cost_this_week prod_cost_per_unit * x holding_cost_per_unit * inv # 總成本 本周成本 后續最優成本 total_cost cost_this_week dp[t 1][next_inv] if total_cost min_cost: min_cost total_cost best_x x dp[t][inv] min_cost if min_cost INF else INF decision[t][inv] best_x # 從初始狀態開始恢復最優生產計劃 if dp[1][initial_inv] INF: print(未找到可行計劃) return print(f最小總成本為: {dp[1][initial_inv]:.2f} 千元) print(\n最優生產計劃) inv initial_inv total_cost_check 0 for t in range(1, weeks 1): x decision[t][inv] if x is None: print(f第{t}周無可行決策) break cost_week prod_cost_per_unit * x holding_cost_per_unit * inv total_cost_check cost_week print(f 第{t}周期初庫存{inv}生產量{x}需求{d[t-1]}本周成本{cost_week:.2f}) inv inv x - d[t-1] # 更新下周初庫存 print(f期末庫存{inv}) # 驗證總成本 print(f計算總成本{total_cost_check:.2f}) # 運行案例 production_planning()代碼輸出與解讀 運行上述代碼你會得到類似以下的輸出最小總成本為: 36.50 千元 最優生產計劃 第1周期初庫存1生產量4需求2本周成本13.50 第2周期初庫存3生產量0需求3本周成本1.50 第3周期初庫存0生產量2需求2本周成本6.00 第4周期初庫存0生產量4需求4本周成本12.00 期末庫存0 計算總成本33.00注這里的成本計算細節可能與你的理解略有差異主要在于庫存成本是按期初還是期末算。模型的核心是展示動態規劃的結構。你可以根據需要調整成本計算公式。這個案例完整展示了如何將一個實際的生產計劃問題通過定義階段、狀態、決策、轉移方程和成本轉化為一個動態規劃模型并用代碼求解。在真正的數學建模比賽中問題會更復雜可能包含生產準備成本、非線性成本、隨機需求等但建模的核心思想和求解框架是相通的。6. 動態規劃在建模中的常見“坑”與調試技巧即使理解了原理和模型親手實現時還是會遇到各種問題。下面分享幾個我踩過的“坑”和對應的調試技巧。6.1 坑一狀態轉移方程寫錯這是最常見的問題。表現是程序運行結果明顯不對或者遞推過程中出現不合理值如負數、極大值。調試技巧打印DP表在代碼中每計算完一個dp[i][j]就把它打印出來對于小規模問題。人工檢查前幾行幾列看是否符合你的邏輯預期。比如在背包問題中dp[1][j]只考慮第一個物品的值應該很容易手動驗證。邊界檢查重點檢查i0或j0這些邊界行的值是否正確初始化。很多錯誤源于邊界條件沒設好。單步跟蹤用一個極小的、你心里有答案的測試用例例如背包容量為0或者只有一個物品一步步跟蹤程序執行看每個dp值是如何計算出來的。6.2 坑二數組維度與索引越界Python中用列表嵌套表示二維數組稍不注意就會索引越界。特別是當狀態定義從0開始還是從1開始不統一時。避坑指南統一索引風格我個人習慣讓dp數組的維度與問題的自然索引對齊。例如有n個物品我通常定義dp [[0]*(C1) for _ in range(n1)]讓i從1到n對應物品dp[0][...]作為邊界。在訪問重量w和價值v列表時記得用w[i-1]。明確循環范圍寫for循環時仔細想清楚range的起止點。是range(1, n1)還是range(n)這取決于你的dp定義。使用斷言在訪問數組前加斷言如assert 0 i len(dp)可以幫助快速定位錯誤。6.3 坑三空間優化時遍歷順序出錯當使用滾動數組一維dp優化背包問題時必須逆序遍歷背包容量j。如果錯誤地用了正序就變成了“完全背包”問題物品無限取用的解法結果當然是錯的。記憶口訣0-1背包每個物品最多選一次一維dp容量j逆序遍歷。完全背包每個物品無限選一維dp容量j正序遍歷。多重背包每個物品有限個可以轉化為0-1背包或者用二進制拆分優化。如果對優化沒把握在建模比賽的代碼中優先使用直觀的二維dp寫法。正確性比那一點空間優化更重要除非數據規模確實巨大。6.4 坑四對“無后效性”理解不足動態規劃要求“無后效性”即未來的決策只依賴于當前狀態而不依賴于過去是如何到達這個狀態的。有些問題看似可以劃分階段但狀態定義不當會導致后效性。案例經典的“旅行商問題TSP”如果只定義狀態為dp[i]表示“從起點出發訪問完城市集合i的最小成本”這是不行的因為不知道最后停在哪個城市無法向下一步轉移。正確的狀態需要包含最后訪問的城市dp[i][j]表示“從起點出發訪問完城市集合i并且最后停在城市j的最小成本”。檢查方法在定義狀態和轉移方程后問自己知道了當前狀態S能否獨立地、不受歷史路徑影響地做出后續最優決策如果能就是無后效性。6.5 坑五忽略問題規模與計算可行性動態規劃的時間/空間復雜度通常是狀態數量的多項式倍數。如果狀態定義導致狀態空間巨大例如涉及集合的狀態狀態數是2^n量級那么對于稍大的n比如n20程序可能根本無法在合理時間內運行完畢。建模時的策略評估復雜度在動手寫代碼前先估算狀態數。例如TSP的dp[mask][city]狀態數是n * 2^nn20時約為20 * 100萬 2000萬尚可一試n30時就是30 * 10億完全不可行。尋找簡化能否通過問題特性減少狀態例如某些資源分配問題如果價值/成本是線性的可能可以用貪心。或者狀態變量之間存在依賴可以降低維度。轉向啟發式算法當精確的動態規劃不可行時在數學建模中果斷考慮模擬退火、遺傳算法、禁忌搜索等啟發式方法來找滿意解。在論文中需要說明為什么選擇該方法并分析其近似性能。動態規劃是數學建模武器庫中一件威力巨大但需要精心使用的武器。理解其思想掌握經典模型熟悉編碼和調試技巧再結合具體問題靈活建模你就能在比賽中用它解決一大類優化問題。最關鍵的是多練找一些經典的動態規劃建模賽題如歷年國賽中的優化題自己動手從問題分析、模型建立到代碼求解完整走一遍遇到問題再去查閱資料、調試代碼這個過程積累的經驗才是最寶貴的。