龍源期刊網
作者：周靜
**：《矽谷》2023年第15期
摘要本文主要闡述的是動態規劃演算法的基本思想，例舉了一典型例項──「最大價值路線」進行分析講解，結合具體的程式設計**，讓讀者充分了解什麼是動態規劃演算法。關鍵詞動態規劃；遞推；最優解
中圖分類號：tp301文獻標識碼：a文章編號：1671-7597（2013）15-0182-02
動態規劃法將待求解問題分解成若干相互重疊的子問題，每個子問題對應決策過程的乙個階段，一般來說，子問題的重疊關係表現在對給定問題求解的遞推關係上（也就是動態規劃函式）中，將子問題的解一次填入表中，當需要再次求解子問題時，可以通過查表獲得該子問題的解而不用再次求解，從而避免了大量重複計算。
動態規劃演算法求解的問題具有兩個特徵：1）能夠分解為相互重疊的若干子問題。2）滿足最優性原理（也稱最優子結構性質）：
該問題的最優解中也包含著其子問題的最優解。動態規劃法設計演算法一般分成三個階段：1）分段。
將原問題分解為若干相互重疊的子問題。2）分析。分析問題是否滿足最優原理，找出動態規劃函式的遞推式。
3）求解。利用遞推式計算，實現動態規劃過程。
動態規劃法利用問題的最優原理，以自底向上的方式，即從子問題的最優解逐步構造出整個問題的最優解。
我們就「求最大價值路線圖」的例項來進行分析，如圖1所示。參考文獻
[1]謬慧芬，邵小兵.動態規劃演算法的原理及應用[j].中國科技資訊，2005（21）.
動態規劃演算法
首先，我們來觀察一下這個演算法。在求從b1到e的最短距離的時候，先求出從c2到e的最短距離 而在求從b2到e的最短距離的時候，又求了一遍從c2到e的最短距離。也就是說，從c2到e的最短距離我們求了兩遍。同樣可以發現，在求從c1 c2到e的最短距離的過程中，從d1到e的最短距離也被求了兩遍。而在整個程...
5動態規劃演算法習題答案
1 最大子段和問題 給定整數序列，求該序列形如的子段和的最大值 1 已知乙個簡單演算法如下 int maxsum int n,int a,int best i,int bestj return sum 試分析該演算法的時間複雜性。2 試用分治演算法解最大子段和問題，並分析演算法的時間複雜性。3 試說...
揹包問題的動態規劃演算法
1.u1 c 2.m n 1時，fm u 恒為0 3.u 0時，fm u 為0 狀態轉移方程為u k 1 uk xk wk。動態規劃基本方程為 wm u時，fm u f m 1 u 否則fm u 為f m 1 u與f m 1 u wm pm中的較大者。定義 n 1 c矩陣f，其m行u列處為fm u ...