動態規劃編程

1. 我是PASCAL的菜鳥，動態規劃學的一塌糊塗，希望各位大俠指導一下動規要怎麼做

1.1 多階段決策過程的最優化問題
1、問題的提出

首先，例舉一個典型的且很直觀的多階段決策問題:
[例] 下圖表示城市之間的交通路網，線段上的數字表示費用，單向通行由A->E。求A->E的最省費用。

如圖從A到E共分為4個階段，即第一階段從A到B，第二階段從B到C，第三階段從C到D，第四階段從D到E。除起點A和終點E外，其它各點既是上一階段的終點又是下一階段的起點。例如從A到B的第一階段中，A為起點，終點有B1，B2，B3三個，因而這時走的路線有三個選擇，一是走到B1，一是走到B2，一是走到B3。若選擇B2的決策，B2就是第一階段在我們決策之下的結果，它既是第一階段路線的終點，又是第二階段路線的始點。在第二階段，再從B2點出發，對於B2點就有一個可供選擇的終點集合(C1，C2，C3)；若選擇由B2走至C2為第二階段的決策，則C2就是第二階段的終點，同時又是第三階段的始點。同理遞推下去，可看到各個階段的決策不同，線路就不同。很明顯，當某階段的起點給定時，它直接影響著後面各階段的行進路線和整個路線的長短，而後面各階段的路線的發展不受這點以前各階段的影響。故此問題的要求是：在各個階段選取一個恰當的決策，使由這些決策組成的一個決策序列所決定的一條路線，其總路程最短。具體情況如下：

（1）由目標狀態E向前推，可以分成四個階段，即四個子問題。如上圖所示。

（2）策略：每個階段到E的最省費用為本階段的決策路徑。

（3）D1，D2是第一次輸人的結點。他們到E都只有一種費用，在D1框上面標5，D2框上面標2。目前無法定下，那一個點將在全程最優策略的路徑上。第二階段計算中，5，2都應分別參加計算。
（4）C1，C2，C3是第二次輸入結點，他們到D1，D2各有兩種費用。此時應計算C1，C2，C3分別到E的最少費用。
C1的決策路徑是 min{（C1D1），（C1D2）}。計算結果是C1+D1+E，在C1框上面標為8。
同理C2的決策路徑計算結果是C2+D2+E，在C2框上面標為7。
同理C3的決策路徑計算結果是C3+D2+E，在C3框上面標為12。
此時也無法定下第一，二階段的城市那二個將在整體的最優決策路徑上。
（5）第三次輸入結點為B1，B2，B3，而決策輸出結點可能為C1，C2，C3。仿前計算可得Bl，B2，B3的決策路徑為如下情況。
Bl:B1C1費用 12+8=20， 路徑:B1+C1+D1+E
B2:B2C1費用 6+8=14， 路徑:B2+C1+D1+E
B3:B2C2費用 12+7=19， 路徑:B3+C2+D2+E
此時也無法定下第一，二，三階段的城市那三個將在整體的最優決策路徑上。
（6）第四次輸入結點為A，決策輸出結點可能為B1，B2，B3。同理可得決策路徑為
A：AB2，費用5+14=19，路徑 A+B2+C1+D1+E。
此時才正式確定每個子問題的結點中，那一個結點將在最優費用的路徑上。19將結果顯然這種計算方法，符合最優原理。子問題的決策中，只對同一城市（結點）比較優劣。而同一階段的城市（結點）的優劣要由下一個階段去決定。
1.2 動態規劃的概念
在上例的多階段決策問題中，各個階段採取的決策，一般來說是與時間有關的，決策依賴於當前狀態，又隨即引起狀態的轉移，一個決策序列就是在變化的狀態中產生出來的，故有「動態」的含義，稱這種解決多階段決策最優化問題的方法為動態規劃方法。

與窮舉法相比，動態規劃的方法有兩個明顯的優點:
(1)大大減少了計算量
(2)豐富了計算結果
從上例的求解結果中，我們不僅得到由A點出發到終點E的最短路線及最短距離，而且還得到了從所有各中間點到終點的最短路線及最短距離，這對許多實際問題來講是很有用的。

動態規劃的最優化概念是在一定條件下，我到一種途徑，在對各階段的效益經過按問題具體性質所確定的運算以後，使得全過程的總效益達到最優。
應用動態規劃要注意階段的劃分是關鍵，必須依據題意分析，尋求合理的劃分階段(子問題)方法。而每個子問題是一個比原問題簡單得多的優化問題。而且每個子問題的求解中，均利用它的一個後部子問題的最優化結果，直到最後一個子問題所得最優解，它就是原問題的最優解。
1.3 動態規劃適合解決什麼樣的問題
准確地說，動態規劃不是萬能的，它只適於解決一定條件的最優策略問題。
或許，大家聽到這個結論會很失望：其實，這個結論並沒有削減動態規劃的光輝，因為屬於上面范圍內的問題極多，還有許多看似不是這個范圍中的問題都可以轉化成這類問題。
上面所說的「滿足一定條件」主要指下面兩點：
(1)狀態必須滿足最優化原理；
(2)狀態必須滿足無後效性。
動態規劃的最優化原理是無論過去的狀態和決策如何，對前面的決策所形成的當前狀態而言，餘下的諸決策必須構成最優策略。 可以通俗地理解為子問題的局部最優將導致整個問題的全局最優在上例中例題1最短路徑問題中，A到E的最優路徑上的任一點到終點E的路徑也必然是該點到終點E的一條最優路徑，滿足最優化原理。

動態規劃的無後效性原則某階段的狀態一旦確定，則此後過程的演變不再受此前各狀態及決策的影響。也就是說，「未來與過去無關」，當前的狀態是此前歷史的一個完整總結，此前的歷史只能通過當前的狀態去影響過程未來的演變。具體地說，如果一個問題被劃分各個階段之後，階段 I 中的狀態只能由階段 I+1 中的狀態通過狀態轉移方程得來，與其他狀態沒有關系，特別是與未發生的狀態沒有關系，這就是無後效性。

1.1 多階段決策過程的最優化問題
1、問題的提出

首先，例舉一個典型的且很直觀的多階段決策問題:
[例] 下圖表示城市之間的交通路網，線段上的數字表示費用，單向通行由A->E。求A->E的最省費用。

2.1 為什麼要用動態規劃法解題
首先，看下面一個問題:

【例題1】數字三角形問題。

7

3 8

8 1 0

2 7 7 4

5 5 2 6 5

示出了一個數字三角形寶塔。數字三角形中的數字為不超過100的正整數。現規定從最頂層走到最底層，每一步可沿左斜線向下或右斜線向下走。假設三角形行數≤100，編程求解從最頂層走到最底層的一條路徑，使得沿著該路徑所經過的數字的總和最大，輸出最大值。輸人數據：由文件輸入數據，文件第一行是三角形的行數N。以後的N行分別是從最頂層到最底層的每一層中的數字。
如輸入： 5
7
3 8
8 1 0
2 7 7 4
4 5 2 6 5
輸出：30
【分析】對於這一問題，很容易想到用枚舉的方法（深度搜索法）去解決，即列舉出所有路徑並記錄每一條路徑所經過的數字總和。然後尋找最大的數字總和，這一想法很直觀，很容易編程實現其程序如下：

program sjx;
const maxn=10;
var
a:array[1..maxn,1..maxn] of integer;
max:longint;
n,i,j:integer;
fname:string;

inputf:text;

procere try(x,y,dep:integer;sum:longint);
begin
if (dep=n) then
begin
if sum>max then max:=sum;
exit
end;
try(x+1,y,dep+1,sum+a[x+1,y]);
try(x+1,y+1,dep+1,sum+a[x+1,y+1]);
end;
begin
readln(fname);

assign(inputf,fname);

reset(inputf);

readln(inputf,n);
for i:=1 to n do
for j:= 1 to i do
read(inputf,a[i,j]);
max:=0;
try(1,1,1,a[1,1]);
writeln(max);
end.

但是當行數很大時，當三角形的行數等於100時，其枚舉量之大是可想而知的，用枚舉法肯定超時，甚至根本不能得到計算結果，必須用動態規劃法來解。
2.2 怎樣用動態規劃法解題
1.逆推法:

按三角形的行劃分階段，若行數為 n，則可把問題看做一個n-1個階段的決策問題。先求出第n-1階段(第n-1行上各點)到第n行的的最大和，再依次求出第n-2階段、第n-3階段……第1階段(起始點)各決策點至第n行的最佳路徑。
設：f[i,j]為從第i階段中的點j至第n行的最大的數字和；
則: f[n,j]=a[n,j] 1<=j<=n

f[i,j]=max{a[i,j]+f[i+1,j],a[i,j]+f[i+1,j+1]} 1<=j<=i.

f[1,1]即為所求。

程序如下：

program datasjx;
const maxn=100;
var
fname:string;
inputf:text;
n,i,j:integer;
a:array[1..maxn,1..maxn] of integer;
f:array[1..maxn,1..maxn] of integer;
begin
readln(fname);
assign(inputf,fname);
reset(inputf);
readln(inputf,n);
for i:=1 to n do
for j:=1 to i do
read(inputf,a[i,j]);
for i:=1 to n do
f[n,i]:=a[n,i];
for i:=n-1 downto 1 do
for j:=1 to i do
if f[i+1,j]>f[i+1,j+1] then f[i,j]:=a[i,j]+f[i+1,j]
else f[i,j]:=a[i,j]+f[i+1,j+1];
writeln(f[1,1]);
end.

2. 順推法

按三角形的行劃分階段，若行數為 n，則可把問題看做一個n-1個階段的決策問題。先求第2行各元素到起點的最大和

,再依次求出第3,4，5,......,.n-1,n到起點的最大和,最後找第n行的最大值

設f[i,j]為 第i行第j列上點到起點的最大和

則 f[1，1]=a[1,1];

f[i，1]=a[i, 1]+f[i-1,1];

f[ i，j ]=max{ a[i,j]+f[i-1,j-1],a[i,j]+f[i-1,j]} 2<=j<=i

max(f[n,1],f[n,2],.......,f[n,n]}即為所求。

程序如下：

program datasjx;
const maxn=100;
var
fname:string;
inputf:text;
n,i,j:integer;
a:array[1..maxn,1..maxn] of integer;
f:array[1..maxn,1..maxn] of integer;
maxsum:integer;
begin
readln(fname);
assign(inputf,fname);
reset(inputf);
readln(inputf,n);
for i:=1 to n do
for j:=1 to i do
read(inputf,a[i,j]);
fillchar(f,sizeof(f),0);

f[1,1]:=a[1,1];
for i:=2 to n do
begin
f[i,1]:=a[i,1]+f[i-1,1];
for j:=2 to i do
if f[i-1,j-1]>f[i-1,j] then f[i,j]:=a[i,j]+f[i-1,j-1]
else f[i,j]:=a[i,j]+f[i-1,j];
end;
maxsum:=0;
for i:=1 to n do
if f[n,i]>maxsum then maxsum:=f[n,i];
writeln(maxsum);
end.

說明一下：

1.用動態規劃解題主要思想是用空間換時間.

2.本題如果n較大，用2維數組空間可能不夠,可以使用1維數組.

程序如下:

program datasjx;
const maxn=100;
var
fname:string;
inputf:text;
n,i,j:integer;
a:array[1..maxn,1..maxn] of integer;
f:array[1..maxn] of integer;
maxsum:integer;
begin
readln(fname);
assign(inputf,fname);
reset(inputf);
readln(inputf,n);
for i:=1 to n do
for j:=1 to i do
read(inputf,a[i,j]);
fillchar(f,sizeof(f),0);
f[1]:=a[1,1];
for i:=2 to n do
begin
for j:=i downto 2 do
if f[j-1]>f[j] then f[j]:=a[i,j]+f[j-1]
else f[j]:=a[i,j]+f[j];
f[1]:=a[i,1]+f[1];
end;
maxsum:=0;
for i:=1 to n do
if f[i]>maxsum then maxsum:=f[i];
writeln(maxsum);
end.

練習:用一維數組和逆推法解本題.

2.3 用動態規劃法解題的一般模式

動態規劃所處理的問題是一個多階段決策問題，一般由初始狀態開始，通過對中間階段決策的選擇，達到結束狀態。這些決策形成了一個決策序列，同時確定了完成整個過程的一條活動路線(通常是求最優的活動路線)。如圖所示。動態規劃的設計都有著一定的模式，一般要經歷以下幾個步驟。
┌———┐┌———┐┌———┐
初始狀態→│決策1│→│決策2│→…→│決策n│→結束狀態
└———┘└———┘└———┘
(1)劃分階段：按照問題的時間或空間特徵，把問題分為若干個階段。在劃分階段時，注意劃分後的階段一定要是有序的或者是可排序的，否則問題就無法求解。
(2)確定狀態和狀態變數：將問題發展到各個階段時所處於的各種客觀情況用不同的狀態表示出來。當然，狀態的選擇要滿足無後效性。
(3)確定決策並寫出狀態轉移方程：因為決策和狀態轉移有著天然的聯系，狀態轉移就是根據上一階段的狀態和決策來導出本階段的狀態。所以如果確定了決策，狀態轉移方程也就可寫出。但事實上常常是反過來做，根據相鄰兩段各狀態之間的關系來確定決策。
(4)尋找邊界條件：給出的狀態轉移方程是一個遞推式，需要一個遞推的終止條件或邊界條件。
(5)程序設計實現：動態規劃的主要難點在於理論上的設計，一旦設計完成，實現部分就會非常簡單。
根據上述動態規劃設計的步驟，可得到大體解題框架如下:

1.初始化(邊界條件)

2.for i:=2 to n (順推法) 或 for i:=n-1 to 1(逆推法)

對i階段的每一個決策點求局部最優

3.確定和輸出結束狀態的值.

2. Python之動態規劃演算法

動態規劃演算法中是將復雜問題遞歸分解為子問題，通過解決這皮拆些子問題來解決復雜問題。與遞歸演算法相比，動態編程減少了堆棧的使用，避免了重復的計算，效率得到顯著提升。

先來看一個簡單的例子，斐波那契數列.

斐波那契數列的定義如下。

斐波那契數列可以很容易地用遞歸演算法實現：

上述代碼，隨燃旁棗著n的增加，計算量呈指數級增長，演算法的時間復雜度是 。

採用動態規劃演算法，通過自下而上的計算數列的值，可以使演算法復雜度減小到 ，代碼如下。

下面我們再看一個復雜一些的例子。

這是小學奧數常見的硬幣問題： 已知有1分，2分，5分三種硬幣數量不限，用這些硬幣湊成為n分錢，那麼一共有多少種組合方法。

我們將硬幣的種類用列表 coins 定義；
將問題定義為一個二維數組 dp，dp[amt][j] 是使用 coins 中前 j+1 種硬幣( coins[0:j+1] )湊成總價amt的組合數。

例如： coins = [1,2,5]

dp[5][1] 就是使用前兩種硬幣 [1,2] 湊成總和為5的組合數。

對於所有的 dp[0][j] 來說，湊成總價為0的情況只有一種，就是所有的硬幣數量都為0。所以對於在有效范圍內任意的j，都有 dp[0][j] 為1。

對於 dp[amt][j] 的計算，也就是使用 coins[0:j+1] 硬幣總價amt的組合數，包含兩種情況計算：

1.當使用第j個硬幣時，有 dp[amt-coins[j]][j] 種情況，即amt減去第j個硬幣幣值，使用前j+1種硬幣的組合數；

2.當不使用第j個硬幣時，有 dp[amt][j-1] 種情況，即使用前j種硬幣湊成amt的組合數；

所以： dp[amt][j] = dp[amt - coins[j]][j]+dp[amt][j-1]

我們最終得到的結果是：dp[amount][-1]

上述分析省略了一些邊界情況。

有了上述的分析，代碼實現就比較簡單了。

動態規劃演算法代碼簡潔，執行效率高。但是與遞歸演算法相比，需要仔細考慮如何分解問題，動態規劃代碼與遞歸調用相比，較難理解。

我把遞歸演算法啟瞎實現的代碼也附在下面。有興趣的朋友可以比較一下兩種演算法的時間復雜度有多大差別。

上述代碼在Python 3.7運行通過。

3. 動態規劃一般用什麼編程有什麼學習好材料嗎

動態規劃屬於數據結構部分，程序=數據結構+演算法，語言只是一種工具，當明白了動態規劃的思路後使用任何一種語言和編程軟體都可以寫動態規劃的程序。

4. 璇烽棶鏈夊摢浣嶅彲浠ュ憡璇夋垜鍔ㄦ佽勫垝閮藉彲浠ョ敤鍝浜涙潵緙栫▼瑙ｅ喅錛

涓銆佷負浠涔堢敤鍔ㄦ佸唴瀛樺垎閰

浣嗘垜浠鏈瀛︿範閾捐〃鐨勬椂鍊欙紝濡傛灉瑕佸瓨鍌ㄦ暟閲忔瘮杈冨氱殑鍚岀被鍨嬫垨鍚岀粨鏋勭殑鏁版嵁鐨勬椂鍊欙紝鎬繪槸浣跨敤涓涓鏁扮粍銆傛瘮濡傝存垜浠瑕佸瓨鍌ㄤ竴涓鐝綰у︾敓鐨勬煇縐戝垎鏁幫紝鎬繪槸瀹氫箟涓涓猣loat鍨嬶紙瀛樺湪0.5鍒嗭級鏁扮粍錛

float score[30];

浣嗘槸錛屽湪浣跨敤鏁扮粍鐨勬椂鍊欙紝鎬繪湁涓涓闂棰樺洶鎵扮潃鎴戜滑錛氭暟緇勫簲璇ユ湁澶氬ぇ錛

鍦ㄥ緢澶氱殑鎯呭喌涓嬶紝浣犲苟涓嶈兘紜瀹氳佷嬌鐢ㄥ氬ぇ鐨勬暟緇勶紝姣斿備笂渚嬶紝浣犲彲鑳藉苟涓嶇煡閬撹ョ彮綰х殑瀛︾敓鐨勪漢鏁幫紝閭ｄ箞浣犲氨瑕佹妸鏁扮粍瀹氫箟寰楄凍澶熷ぇ銆傝繖鏍鳳紝浣犵殑紼嬪簭鍦ㄨ繍琛屾椂灝辯敵璇蜂簡鍥哄畾澶у皬鐨勪綘璁や負瓚沖熷ぇ鐨勫唴瀛樼┖闂淬傚嵆浣誇綘鐭ラ亾璇ョ彮綰х殑瀛︾敓鏁幫紝浣嗘槸濡傛灉鍥犱負鏌愮嶇壒孌婂師鍥犱漢鏁版湁澧炲姞鎴栬呭噺灝戱紝浣犲張蹇呴』閲嶆柊鍘諱慨鏀圭▼搴忥紝鎵╁ぇ鏁扮粍鐨勫瓨鍌ㄨ寖鍥淬傝繖縐嶅垎閰嶅滻瀹氬ぇ灝忕殑鍐呭瓨鍒嗛厤鏂規硶縐頒箣涓洪潤鎬佸唴瀛樺垎閰嶃備絾鏄榪欑嶅唴瀛樺垎閰嶇殑鏂規硶瀛樺湪姣旇緝涓ラ噸鐨勭己闄鳳紝鐗瑰埆鏄澶勭悊鏌愪簺闂棰樻椂錛氬湪澶у氭暟鎯呭喌涓嬩細嫻璐瑰ぇ閲忕殑鍐呭瓨絀洪棿錛屽湪灝戞暟鎯呭喌涓嬶紝褰撲綘瀹氫箟鐨勬暟緇勪笉澶熷ぇ鏃訛紝鍙鑳藉紩璧蜂笅鏍囪秺鐣岄敊璇錛岀敋鑷沖艱嚧涓ラ噸鍚庢灉銆

閭ｄ箞鏈夋病鏈夊叾瀹冪殑鏂規硶鏉ヨВ鍐寵繖鏍風殑澶栧憿浣撳憿錛熸湁錛岄偅灝辨槸鍔ㄦ佸唴瀛樺垎閰嶃

鎵璋撳姩鎬佸唴瀛樺垎閰嶅氨鏄鎸囧湪紼嬪簭鎵ц岀殑榪囩▼涓鍔ㄦ佸湴鍒嗛厤鎴栬呭洖鏀跺瓨鍌ㄧ┖闂寸殑鍒嗛厤鍐呭瓨鐨勬柟娉曘傚姩鎬佸唴瀛樺垎閰嶄笉璞℃暟緇勭瓑闈欐佸唴瀛樺垎閰嶆柟娉曢偅鏍烽渶瑕侀勫厛鍒嗛厤瀛樺偍絀洪棿錛岃屾槸鐢辯郴緇熸牴鎹紼嬪簭鐨勯渶瑕佸嵆鏃跺垎閰嶏紝涓斿垎閰嶇殑澶у皬灝辨槸紼嬪簭瑕佹眰鐨勫ぇ灝忋備粠浠ヤ笂鍔ㄣ侀潤鎬佸唴瀛樺垎閰嶆瘮杈冨彲浠ョ煡閬撳姩鎬佸唴瀛樺垎閰嶇浉瀵逛簬鏅娉板唴瀛樺垎閰嶇殑鐗圭偣錛

1銆佷笉闇瑕侀勫厛鍒嗛厤瀛樺偍絀洪棿錛

2銆佸垎閰嶇殑絀洪棿鍙浠ユ牴鎹紼嬪簭鐨勯渶瑕佹墿澶ф垨緙╁皬銆

浜屻佸備綍瀹炵幇鍔ㄦ佸唴瀛樺垎閰嶅強鍏剁＄悊

瑕佸疄鐜版牴鎹紼嬪簭鐨勯渶瑕佸姩鎬佸垎閰嶅瓨鍌ㄧ┖闂達紝灝卞繀欏葷敤鍒頒互涓嬪嚑涓鍑芥暟

1銆乵alloc鍑芥暟

malloc鍑芥暟鐨勫師鍨嬩負錛

void *malloc (unsigned int size)

鍏朵綔鐢ㄦ槸鍦ㄥ唴瀛樼殑鍔ㄦ佸瓨鍌ㄥ尯涓鍒嗛厤涓涓闀垮害涓簊ize鐨勮繛緇絀洪棿銆傚叾鍙傛暟鏄涓涓鏃犵﹀彿鏁村艦鏁幫紝榪斿洖鍊兼槸涓涓鎸囧悜鎵鍒嗛厤鐨勮繛緇瀛樺偍鍩熺殑璧峰嬪湴鍧鐨勬寚閽堛傝繕鏈変竴鐐瑰繀欏繪敞鎰忕殑鏄錛屽綋鍑芥暟鏈鑳芥垚鍔熷垎閰嶅瓨鍌ㄧ┖闂達紙濡傚唴瀛樹笉瓚籌級灝變細榪斿洖涓涓狽ULL鎸囬拡銆傛墍浠ュ湪璋冪敤璇ュ嚱鏁版椂搴旇ユ嫻嬭繑鍥炲兼槸鍚︿負NULL騫舵墽琛岀浉搴旂殑鎿嶄綔銆

涓嬩緥鏄涓涓鍔ㄦ佸垎閰嶇殑紼嬪簭錛

#include
#include
main()
{
int count,*array; /*count鏄涓涓璁℃暟鍣錛宎rray鏄涓涓鏁村瀷鎸囬拡錛屼篃鍙浠ョ悊瑙ｄ負鎸囧悜涓涓鏁村瀷鏁扮粍鐨勯栧湴鍧*/
if((array(int *) malloc(10*sizeof(int)))==NULL)
{
printf("涓嶈兘鎴愬姛鍒嗛厤瀛樺偍絀洪棿銆");
exit(1);
}
for (count=0;count銆10;count++) /*緇欐暟緇勮祴鍊*/
array[count]=count;
for(count=0;count銆10;count++) /*鎵撳嵃鏁扮粍鍏冪礌*/
printf("%2d",array[count]);
}

涓婁緥涓鍔ㄦ佸垎閰嶄簡10涓鏁村瀷瀛樺偍鍖哄煙錛岀劧鍚庤繘琛岃祴鍊煎苟鎵撳嵃銆備緥涓璱f((array(int *) malloc(10*sizeof(int)))==NULL)璇鍙ュ彲浠ュ垎涓轟互涓嬪嚑姝ワ細

1錛夊垎閰10涓鏁村瀷鐨勮繛緇瀛樺偍絀洪棿錛屽苟榪斿洖涓涓鎸囧悜鍏惰搗濮嬪湴鍧鐨勬暣鍨嬫寚閽

2錛夋妸姝ゆ暣鍨嬫寚閽堝湴鍧璧嬬粰array

3錛夋嫻嬭繑鍥炲兼槸鍚︿負NULL

2銆乫ree鍑芥暟

鐢變簬鍐呭瓨鍖哄煙鎬繪槸鏈夐檺鐨勶紝涓嶈兘涓嶉檺鍒跺湴鍒嗛厤涓嬪幓錛岃屼笖涓涓紼嬪簭瑕佸敖閲忚妭鐪佽祫婧愶紝鎵浠ュ綋鎵鍒嗛厤鐨勫唴瀛樺尯鍩熶笉鐢ㄦ椂錛屽氨瑕侀噴鏀懼畠錛屼互渚垮叾瀹冪殑鍙橀噺鎴栬呯▼搴忎嬌鐢ㄣ傝繖鏃舵垜浠灝辮佺敤鍒癴ree鍑芥暟銆

鍏跺嚱鏁板師鍨嬫槸錛

void free(void *p)

浣滅敤鏄閲婃斁鎸囬拡p鎵鎸囧悜鐨勫唴瀛樺尯銆

鍏跺弬鏁皃蹇呴』鏄鍏堝墠璋冪敤malloc鍑芥暟鎴朿alloc鍑芥暟錛堝彟涓涓鍔ㄦ佸垎閰嶅瓨鍌ㄥ尯鍩熺殑鍑芥暟錛夋椂榪斿洖鐨勬寚閽堛傜粰free鍑芥暟浼犻掑叾瀹冪殑鍊煎緢鍙鑳介犳垚姝繪満鎴栧叾瀹冪伨闅炬х殑鍚庢灉銆

娉ㄦ剰錛氳繖閲岄噸瑕佺殑鏄鎸囬拡鐨勫礆紝鑰屼笉鏄鐢ㄦ潵鐢寵峰姩鎬佸唴瀛樼殑鎸囬拡鏈韜銆備緥錛

int *p1,*p2;
p1=malloc(10*sizeof(int));
p2=p1;
鈥︹
free(p2) /*鎴栬協ree(p2)*/

malloc榪斿洖鍊艱祴緇檖1錛屽張鎶妏1鐨勫艱祴緇檖2錛屾墍浠ユゆ椂p1錛宲2閮藉彲浣滀負free鍑芥暟鐨勫弬鏁般

malloc鍑芥暟鏄瀵瑰瓨鍌ㄥ尯鍩熻繘琛屽垎閰嶇殑銆

free鍑芥暟鏄閲婃斁宸茬粡涓嶇敤鐨勫唴瀛樺尯鍩熺殑銆

鎵浠ョ敱榪欎袱涓鍑芥暟灝卞彲浠ュ疄鐜板瑰唴瀛樺尯鍩熻繘琛屽姩鎬佸垎閰嶅苟榪涜岀畝鍗曠殑綆＄悊浜嗐

5. 什麼是動態規劃

動態規劃演算法 概念及意義動態規劃(dynamic programming)是運籌學的一個分支，是求解決策過程(decision process)最優化的數學方法。20世紀50年代初美國數學家R.E.Bellman等人在研究多階段決策過程(multistep decision process)的優化問題時，提出了著名的最優化原理(principle of optimality)，把多階段過程轉化為一系列單階段問題，利用各階段之間的關系，逐個求解，創立了解決這類過程優化問題的新方法——動態規劃。1957年出版了他的名著Dynamic Programming，這是該領域的第一本著作。
動態規劃問世以來，在經濟管理、生產調度、工程技術和最優控制等方面得到了廣泛的應用。例如最短路線、庫存管理、資源分配、設備更新、排序、裝載等問題，用動態規劃方法比用其它方法求解更為方便。
雖然動態規劃主要用於求解以時間劃分階段的動態過程的優化問題，但是一些與時間無關的靜態規劃(如線性規劃、非線性規劃)，只要人為地引進時間因素，把它視為多階段決策過程，也可以用動態規劃方法方便地求解。
動態規劃程序設計是對解最優化問題的一種途徑、一種方法，而不是一種特殊演算法。不象前面所述的那些搜索或數值計算那樣，具有一個標準的數學表達式和明確清晰的解題方法。動態規劃程序設計往往是針對一種最優化問題，由於各種問題的性質不同，確定最優解的條件也互不相同，因而動態規劃的設計方法對不同的問題，有各具特色的解題方法，而不存在一種萬能的動態規劃演算法，可以解決各類最優化問題。因此讀者在學習時，除了要對基本概念和方法正確理解外，必須具體問題具體分析處理，以豐富的想像力去建立模型，用創造性的技巧去求解。我們也可以通過對若干有代表性的問題的動態規劃演算法進行分析、討論，逐漸學會並掌握這一設計方法。 基本模型
多階段決策過程的最優化問題。
在現實生活中，有一類活動的過程，由於它的特殊性，可將過程分成若干個互相聯系的階段，在它的每一階段都需要作出決策，從而使整個過程達到最好的活動效果。當然，各個階段決策的選取不是任意確定的，它依賴於當前面臨的狀態，又影響以後的發展，當各個階段決策確定後，就組成一個決策序列，因而也就確定了整個過程的一條活動路線，如圖所示：（看詞條圖）
這種把一個問題看作是一個前後關聯具有鏈狀結構的多階段過程就稱為多階段決策過程，這種問題就稱為多階段決策問題。 記憶化搜索 給你一個數字三角形, 形式如下:
1
2 3
4 5 6
7 8 9 10
找出從第一層到最後一層的一條路,使得所經過的權值之和最小或者最大.
無論對與新手還是老手，這都是再熟悉不過的題了，很容易地，我們寫出狀態轉移方程：f(i, j)=a[i, j] + min{f(i+1, j)，f(i+1, j + 1)}
對於動態規劃演算法解決這個問題，我們根據狀態轉移方程和狀態轉移方向，比較容易地寫出動態規劃的循環表示方法。但是，當狀態和轉移非常復雜的時候，也許寫出循環式的動態規劃就不是那麼簡單了。
解決方法：
我們嘗試從正面的思路去分析問題，如上例，不難得出一個非常簡單的遞歸過程 :
f1:=f(i-1,j+1); f2:=f(i-1,j);
if f1>f2 then f:=f1+a[i,j] else f:=f2+a[i,j];
顯而易見，這個演算法就是最簡單的搜索演算法。時間復雜度為2^n，明顯是會超時的。分析一下搜索的過程，實際上，很多調用都是不必要的，也就是把產生過的最優狀態，又產生了一次。為了避免浪費，很顯然，我們存放一個opt數組：Opt[i, j] - 每產生一個f(i, j)，將f(i, j)的值放入opt中，以後再次調用到f(i, j)的時候，直接從opt[i, j]來取就可以了。於是動態規劃的狀態轉移方程被直觀地表示出來了，這樣節省了思維的難度，減少了編程的技巧，而運行時間只是相差常數的復雜度，避免了動態規劃狀態轉移先後的問題，而且在相當多的情況下，遞歸演算法能更好地避免浪費，在比賽中是非常實用的. 狀態 決策
決策：
當前狀態通過決策,回到了以前狀態.可見決策其實就是狀態之間的橋梁。而以前狀態也就決定了當前狀態的情況。數字三角形的決策就是選擇相鄰的兩個以前狀態的最優值。
狀態：
我們一般在動規的時候所用到的一些數組，也就是用來存儲每個狀態的最優值的。我們就從動態規劃的要訣，也就是核心部分「狀態」開始，來逐步了解動態規劃。有時候當前狀態確定後,以前狀態就已經確定,則無需枚舉.
動態規劃演算法的應用 一、動態規劃的概念
近年來，涉及動態規劃的各種競賽題越來越多，每一年的NOI幾乎都至少有一道題目需要用動態規劃的方法來解決；而競賽對選手運用動態規劃知識的要求也越來越高，已經不再停留於簡單的遞推和建模上了。
要了解動態規劃的概念，首先要知道什麼是多階段決策問題。
1. 多階段決策問題
如果一類活動過程可以分為若干個互相聯系的階段，在每一個階段都需作出決策(採取措施)，一個階段的決策確定以後，常常影響到下一個階段的決策，從而就完全確定了一個過程的活動路線，則稱它為多階段決策問題。
各個階段的決策構成一個決策序列，稱為一個策略。每一個階段都有若干個決策可供選擇，因而就有許多策略供我們選取，對應於一個策略可以確定活動的效果，這個效果可以用數量來確定。策略不同，效果也不同，多階段決策問題，就是要在可以選擇的那些策略中間，選取一個最優策略，使在預定的標准下達到最好的效果.
2．動態規劃問題中的術語
階段：把所給求解問題的過程恰當地分成若干個相互聯系的階段，以便於求解，過程不同，階段數就可能不同．描述階段的變數稱為階段變數。在多數情況下，階段變數是離散的，用k表示。此外，也有階段變數是連續的情形。如果過程可以在任何時刻作出決策，且在任意兩個不同的時刻之間允許有無窮多個決策時，階段變數就是連續的。
在前面的例子中，第一個階段就是點A，而第二個階段就是點A到點B，第三個階段是點B到點C，而第四個階段是點C到點D。
狀態：狀態表示每個階段開始面臨的自然狀況或客觀條件，它不以人們的主觀意志為轉移，也稱為不可控因素。在上面的例子中狀態就是某階段的出發位置，它既是該階段某路的起點，同時又是前一階段某支路的終點。
在前面的例子中，第一個階段有一個狀態即A，而第二個階段有兩個狀態B1和B2，第三個階段是三個狀態C1，C2和C3，而第四個階段又是一個狀態D。
過程的狀態通常可以用一個或一組數來描述，稱為狀態變數。一般，狀態是離散的，但有時為了方便也將狀態取成連續的。當然，在現實生活中，由於變數形式的限制，所有的狀態都是離散的，但從分析的觀點，有時將狀態作為連續的處理將會有很大的好處。此外，狀態可以有多個分量(多維情形)，因而用向量來代表；而且在每個階段的狀態維數可以不同。
當過程按所有可能不同的方式發展時，過程各段的狀態變數將在某一確定的范圍內取值。狀態變數取值的集合稱為狀態集合。
無後效性：我們要求狀態具有下面的性質：如果給定某一階段的狀態，則在這一階段以後過程的發展不受這階段以前各段狀態的影響，所有各階段都確定時，整個過程也就確定了。換句話說，過程的每一次實現可以用一個狀態序列表示，在前面的例子中每階段的狀態是該線路的始點，確定了這些點的序列，整個線路也就完全確定。從某一階段以後的線路開始，當這段的始點給定時，不受以前線路（所通過的點）的影響。狀態的這個性質意味著過程的歷史只能通過當前的狀態去影響它的未來的發展，這個性質稱為無後效性。
決策：一個階段的狀態給定以後，從該狀態演變到下一階段某個狀態的一種選擇（行動）稱為決策。在最優控制中，也稱為控制。在許多間題中，決策可以自然而然地表示為一個數或一組數。不同的決策對應著不同的數值。描述決策的變數稱決策變數，因狀態滿足無後效性，故在每個階段選擇決策時只需考慮當前的狀態而無須考慮過程的歷史。
決策變數的范圍稱為允許決策集合。
策略：由每個階段的決策組成的序列稱為策略。對於每一個實際的多階段決策過程，可供選取的策略有一定的范圍限制，這個范圍稱為允許策略集合。允許策略集合中達到最優效果的策略稱為最優策略。
給定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階段的狀態轉移規律，稱為狀態轉移方程。
最優性原理:作為整個過程的最優策略，它滿足：相對前面決策所形成的狀態而言，餘下的子策略必然構成「最優子策略」。
最優性原理實際上是要求問題的最優策略的子策略也是最優。讓我們通過對前面的例子再分析來具體說明這一點：從A到D，我們知道，最短路徑是A�8�1B1�8�1C2�8�1D，這些點的選擇構成了這個例子的最優策略，根據最優性原理，這個策略的每個子策略應是最優：A�8�1B1�8�1C2是A到C2的最短路徑，B1�8�1C2�8�1D也是B1到D的最短路徑……──事實正是如此，因此我們認為這個例子滿足最優性原理的要求。