近年來，涉及動態規劃的各種競賽題越來越多，而競賽對選手運用動態規劃知識的要求也越來越高，已經不再停留於簡單的遞推和建模上了。
要了解動態規劃的概念，首先要知道什麼是多階段決策問題。
一、多階段決策問題
如果一類活動過程可以分為若干個互相聯絡的階段，在每乙個階段都需作出決策(採取措施)，乙個階段的決策確定以後，常常影響到下乙個階段的決策，從而就完全確定了乙個過程的活動路線，則稱它為多階段決策問題。
各個階段的決策構成乙個決策序列，稱為乙個策略。每乙個階段都有若干個決策可供選擇，因而就有許多策略供我們選取，對應於乙個策略可以確定活動的效果，這個效果可以用數量來確定。策略不同，效果也不同，多階段決策問題，就是要在可以選擇的那些策略中間，選取乙個最優策略，使在預定的標準下達到最好的效果.
讓我們先來看下面的例子：如圖所示的是乙個帶權有向的多段圖，要求從a到d的最短路徑的長度(下面簡稱最短距離)。
我們可以搜尋，列舉圖中的每條路徑，但當圖的規模大起來時，搜尋的效率顯然不可能盡人意。讓我們來試用動態規劃的思路分析這道題：從圖中可以看到，a點要到達d點必然要經過b1和b2中的乙個，所以a到d的最短距離必然等於b1到d的最短距離加上5，或是b2到d的最短距離加上2。
同樣的，b1到d的最短距離必然等於c1到d的最短距離加上3或是c2到d的最短距離加上2，……。
我們設g[i]為點i到點d的距離，顯然g[c1]=4，g[c2]=3，g[c3]=5，根據上面的分析，有：
g[b1]=min=5，
g[b2]=min=9，
再就有g[a]=min=10，
所以a到d的最短距離是10，最短路徑是ab1c2d。
二、動態規劃的術語
1．階段
把所給求解問題的過程恰當地分成若干個相互聯絡的階段，以便於求解，過程不同，階段數就可能不同．描述階段的變數稱為階段變數。在多數情況下，階段變數是離散的，用k表示。此外，也有階段變數是連續的情形。
如果過程可以在任何時刻作出決策，且在任意兩個不同的時刻之間允許有無窮多個決策時，階段變數就是連續的。
在前面的例子中，第乙個階段就是點a，而第二個階段就是點a到點b，第三個階段是點b到點c，而第四個階段是點c到點d。
2．狀態
狀態表示每個階段開始面臨的自然狀況或客觀條件，它不以人們的主觀意志為轉移，也稱為不可控因素。在上面的例子中狀態就是某階段的出發位置，它既是該階段某路的起點，同時又是前一階段某支路的終點。
在前面的例子中，第乙個階段有乙個狀態即a，而第二個階段有兩個狀態b1和b2，第三個階段是三個狀態c1，c2和c3，而第四個階段又是乙個狀態d。
過程的狀態通常可以用乙個或一組數來描述，稱為狀態變數。一般，狀態是離散的，但有時為了方便也將狀態取成連續的。當然，在現實生活中，由於變數形式的限制，所有的狀態都是離散的，但從分析的觀點，有時將狀態作為連續的處理將會有很大的好處。
此外，狀態可以有多個分量(多維情形)，因而用向量來代表；而且在每個階段的狀態維數可以不同。
當過程按所有可能不同的方式發展時，過程各段的狀態變數將在某一確定的範圍內取值。狀態變數取值的集合稱為狀態集合。
3．無後效性
我們要求狀態具有下面的性質：如果給定某一階段的狀態，則在這一階段以後過程的發展不受這階段以前各段狀態的影響，所有各階段都確定時，整個過程也就確定了。換句話說，過程的每一次實現可以用乙個狀態序列表示，在前面的例子中每階段的狀態是該線路的始點，確定了這些點的序列，整個線路也就完全確定。
從某一階段以後的線路開始，當這段的始點給定時，不受以前線路（所通過的點）的影響。狀態的這個性質意味著過程的歷史只能通過當前的狀態去影響它的未來的發展，這個性質稱為無後效性。
4．決策
乙個階段的狀態給定以後，從該狀態演變到下一階段某個狀態的一種選擇（行動）稱為決策。在最優控制中，也稱為控制。在許多問題中，決策可以自然而然地表示為乙個數或一組數。
不同的決策對應著不同的數值。描述決策的變數稱決策變數，因狀態滿足無後效性，故在每個階段選擇決策時只需考慮當前的狀態而無須考慮過程的歷史。
決策變數的範圍稱為允許決策集合。
5．策略
由每個階段的決策組成的序列稱為策略。對於每乙個實際的多階段決策過程，可供選取的策略有一定的範圍限制，這個範圍稱為允許策略集合。允許策略集合中達到最優效果的策略稱為最優策略。
給定k階段狀態變數x(k)的值後，如果這一階段的決策變數一經確定，第k+1階段的狀態變數x(k+1)也就完全確定，即x(k+1)的值隨x(k)和第k階段的決策u(k)的值變化而變化，那麼可以把這一關係看成(x(k)，u(k))與x(k+1)確定的對應關係，用x(k+1)=tk(x(k),u(k))表示。這是從k階段到k+1階段的狀態轉移規律，稱為狀態轉移方程。
6．最優性原理
作為整個過程的最優策略，它滿足：相對前面決策所形成的狀態而言，餘下的子策略必然構成「最優子策略」。
最優性原理實際上是要求問題的最優策略的子策略也是最優。讓我們通過對前面的例子再分析來具體說明這一點：從a到d，我們知道，最短路徑是ab1c2d，這些點的選擇構成了這個例子的最優策略，根據最優性原理，這個策略的每個子策略應是最優：
ab1c2是a到c2的最短路徑，b1c2d也是b1到d的最短路徑……事實正是如此，因此我們認為這個例子滿足最優性原理的要求。
下面我們列舉歷年國內國際競賽的一些典型動態規劃問題加以分析。
動態規劃基本原理
動態程式設計 近年來，涉及動態規劃的各種競賽題越來越多，每一年的noi幾乎都至少有一道題目需要用動態規劃的方法來解決 而競賽對選手運用動態規劃知識的要求也越來越高，已經不再停留於簡單的遞推和建模上了。要了解動態規劃的概念，首先要知道什麼是多階段決策問題。一 多階段決策問題 如果一類活動過程可以分為若...
廣告基本原理
做廣告首先要考慮的是 廣告物件的消費動機和競爭對手的廣告手段。廣告是企業長遠的投資，其效果是永續的，有形無形的影響子子孫孫。廣告的品質反映出產品的品質 四p 商品 路徑 促進 廣告被認為屬於非人員的銷售，當消費者對商品有高度需求時最有效果，廣告是表現商品差異的手段，告知消費者商品潛在特質的重要性，是...
LTE OFDM 基本原理
ofdm基本原理介紹 課程目標 了解ofdm的基本概念 了解ofdm的基本原理 了解ofdm技術的優缺點 理解ofdm的關鍵技術 了解ofdm在上下行鏈路中的應用 知識點無線通道傳播特性 ofdm的基本概念 ofdm的優缺點 與其他通訊通道相比，移動通道是最為複雜的一種。電波傳播的主要方式是空間波，...