首先，我們來觀察一下這個演算法。在求從b1到e的最短距離的時候，先求出從c2到e的最短距離；而在求從b2到e的最短距離的時候，又求了一遍從c2到e的最短距離。也就是說，從c2到e的最短距離我們求了兩遍。
同樣可以發現，在求從c1、c2到e的最短距離的過程中，從d1到e的最短距離也被求了兩遍。而在整個程式中，從d1到e的最短距離被求了四遍。如果在求解的過程中，同時將求得的最短距離"記錄在案"，隨時呼叫，就可以避免這種情況。
於是，可以改進該演算法，將每次求出的從v到e的最短距離記錄下來，在演算法中遞迴地求mindistance(v)時先檢查以前是否已經求過了mindistance(v)，如果求過了則不用重新求一遍，只要查詢以前的記錄就可以了。這樣，由於所有的點有n個，因此不同的狀態數目有n個，該演算法的數量級為o(n)。
更進一步，可以將這種遞迴改為遞推，這樣可以減少遞迴呼叫的開銷。
請看圖1，可以發現，a只和bi相鄰，bi只和ci相鄰,...，依此類推。這樣，我們可以將原問題的解決過程劃分為4個階段，設s1=,s2=,s3=,s4=，fk(u)表示從sk中的點u到e的最短距離，則
並且有邊界條件
顯然可以遞推地求出f1(a)，也就是從a到e的最短距離。這種演算法的複雜度為o(n)，因為所有的狀態總數（節點總數）為n，對每個狀態都只要遍歷一次，而且程式很簡潔。
具體演算法如下：
procedure dynamicprogramming;
begin
f5[e]:=0;
for i:=4 downto 1 do
for each u ∈sk do
begin
fk[u]:=無窮大;
for each v∈sk+1∩δ(u) do
if fk[u]>w(u,v)+fk+1[v] then fk[u]:=w(u,v)+fk+1[v];
end;
輸出f1[a];
end;
這種高效演算法，就是動態規劃演算法。
動態規劃(dynamic programming)是運籌學的乙個分支，是求解決策過程(decision process)最優化的數學方法。20世紀50年代初美國數學家r.e.
bellman等人在研究多階段決策過程(multistep decision process)的優化問題時，提出了著名的最優化原理(principle of optimality)，把多階段過程轉化為一系列單階段問題，逐個求解，創立了解決這類過程優化問題的新方法——動態規劃。2023年出版了他的名著dynamic programming，這是該領域的第一本著作。
動態規劃問世以來，在經濟管理、生產排程、工程技術和最優控制等方面得到了廣泛的應用。例如最短路線、庫存管理、資源分配、裝置更新、排序、裝載等問題，用動態規劃方法比用其它方法求解更為方便。
雖然動態規劃主要用於求解以時間劃分階段的動態過程的優化問題，但是一些與時間無關的靜態規劃(如線性規劃、非線性規劃)，只要人為地引進時間因素，把它視為多階段決策過程，也可以用動態規劃方法方便地求解。
多階段決策過程，是指這樣的一類特殊的活動過程，問題可以按時間順序分解成若干相互聯絡的階段，在每乙個階段都要做出決策，全部過程的決策是乙個決策序列。要使整個活動的總體效果達到最優的問題，稱為多階段決策問題。
例1是乙個多階段決策問題的例子，下面是另乙個多階段決策問題的例子：
[例2] 生產計畫問題
工廠生產某種產品，每單位(千件)的成本為1(千元)，每次開工的固定成本為3(千元)，工廠每季度的最大生產能力為6(千件)。經調查，市場對該產品的需求量第
一、二、
三、四季度分別為 2，3，2，4(千件)。如果工廠在第
一、二季度將全年的需求都生產出來，自然可以降低成本(少付固定成本費)，但是對於第
三、四季度才能上市的產品需付儲存費，每季每千件的儲存費為0.5(千元)。還規定年初和年末這種產品均無庫存。
試制訂乙個生產計畫，即安排每個季度的產量，使一年的總費用(生產成本和儲存費)最少。
根據過程的時間變數是離散的還是連續的，分為離散時間決策過程(discrete-time decision process)，即多階段決策過程和連續時間決策過程(continuous-time decision process)；根據過程的演變是確定的還是隨機的，分為確定性決策過程(deterministic decision process)和隨機性決策過程(stochastic decision process)，其中應用最廣的是確定性多階段決策過程。
乙個多階段決策過程最優化問題的動態規劃模型通常包含以下要素：
1.階段
階段(step)是對整個過程的自然劃分。通常根據時間順序或空間特徵來劃分階段，以便按階段的次序解優化問題。階段變數一般用k=1,2,..
,n表示。在例1中由a出發為k=1，由bi(i=1,2)出發為k=2，依此下去從di(i=1,2,3)出發為k=4，共n=4個階段。在例2中按照第
一、二、
三、四季度分為k=1,2,3,4，共4個階段。
2.狀態
狀態(state)表示每個階段開始時過程所處的自然狀況。它應該能夠描述過程的特徵並且具有無後向性，即當某階段的狀態給定時，這個階段以後過程的演變與該階段以前各階段的狀態無關，即每個狀態都是過去歷史的乙個完整總結。通常還要求狀態是直接或間接可以觀測的。
描述狀態的變數稱狀態變數(state variable)。變數允許取值的範圍稱允許狀態集合(set of admissible states)。用xk表示第k階段的狀態變數，它可以是乙個數或乙個向量。
用xk表示第k階段的允許狀態集合。在例1中x2可取b1，b2，x2=。
n個階段的決策過程有n+1個狀態變數，xn+1表示xn演變的結果，在例1中x5取e。
根據過程演變的具體情況，狀態變數可以是離散的或連續的。為了計算的方便有時將連續變數離散化；為了分析的方便有時又將離散變數視為連續的。
狀態變數簡稱為狀態。
3.決策
當乙個階段的狀態確定後，可以作出各種選擇從而演變到下一階段的某個狀態，這種選擇手段稱為決策(decision)，在最優控制問題中也稱為控制(control)。
描述決策的變數稱決策變數(decision variable)。變數允許取值的範圍稱允許決策集合(set of admissible decisions)。用uk(xk)表示第k階段處於狀態xk時的決策變數，它是xk的函式，用uk(xk)表示了xk的允許決策集合。
在例1中u2(b1)可取c1,c2,c3。
決策變數簡稱決策。
4.策略
決策組成的序列稱為策略(policy)。由初始狀態x1開始的全過程的策略記作p1n(x1)，即p1n(x1)=。由第k階段的狀態xk開始到終止狀態的後部子過程的策略記作pkn(xk)，即pkn(xk)=。
類似地，由第k到第j階段的子過程的策略記作pkj(xk)=。對於每乙個階段k的某一給定的狀態xk，可供選擇的策略pkj(xk)有一定的範圍，稱為允許策略集合(set of admissible policies)，用p1n(x1),pkn(xk),pkj(xk)表示。
5.狀態轉移方程
在確定性過程中，一旦某階段的狀態和決策為已知，下階段的狀態便完全確定。用狀態轉移方程(equation of state)表示這種演變規律，寫作
在例1中狀態轉移方程為：xk+1=uk(xk)
6.指標函式和最優值函式
指標函式(objective function)是衡量過程優劣的數量指標，它是關於策略的數量函式，從階段k到階段n的指標函式用vkn(xk,pkn(xk))表示，k=1,2,...,n。
能夠用動態規劃解決的問題的指標函式應具有可分離性，即vkn可表為xk,uk,vk+1 n 的函式，記為：
其中函式是乙個關於變數vk+1 n單調遞增的函式。這一性質保證了最優化原理(principle of optimality)的成立，是動態規劃的適用前提。
過程在第j 階段的階段指標取決於狀態xj和決策uj，用vj(xj,uj)表示。階段k到階段n的指標由vj(j=k,k+1,..n)組成，常見的形式有：
階段指標之和，即
階段指標之積，即
階段指標之極大(或極小)，即
這些形式下第k到第j階段子過程的指標函式為vkj(xk,uk,xk+1,...,xj+1)。可以發現，上述(3)-(5)三個指標函式的形式都滿足最優性原理。
在例1中指標函式為(3)的形式，其中vj(xj,uj)是邊的權（邊的長度）,uj(xj)表示從xj出發根據決策uj(xj)下一步所到達的節點。
根據狀態轉移方程，指標函式vkn還可以表示為狀態xk和策略pkn的函式，即vkn(xk,pkn)。在xk給定時指標函式vkn對pkn的最優值稱為最優值函式(optimal value function)，記作fk(xk)，即
其中opt可根據具體情況取max或min。上式的意義是，對於某個階段k的某個狀態xk，。
7.最優策略和最優軌線
使指標函式vkn達到最優值的策略是從k開始的後部子過程的最優策略，記作pkn*=,p1n*又是全過程的最優策略，簡稱最優策略(optimal policy)。從初始狀態x1(=x1*)出發，過程按照p1n*和狀態轉移方程演變所經歷的狀態序列稱最優軌線(optimal trajectory)。
動態規劃發展的早期階段，從簡單邏輯出發給出了所謂最優性原理，然後在最優策略存在的前提下匯出基本方程，再由這個方程求解最優策略。後來在動態規劃的應用過程中發現，最優性原理不是對任何決策過程普遍成立，它與基本方程不是無條件等價，二者之間也不存在任何確定的蘊含關係。基本方程在動態規劃中起著更為本質的作用。
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 ...
實驗二動態規劃演算法的應用
一 實驗目的 2 二 實驗內容 2 2.1數塔問題 2 2.2 最長單調遞增子串行問題 2 三 演算法設計 2 3.1 數塔問題 2 3.1.1演算法描述 2 3.1.2 函式設計 3 3.2 最長單調遞增子串行問題 3 3.1.1演算法描述 3 3.1.2 函式設計 3 四.程式除錯及執行結果分析...