动态规划编程

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的最短路径……──事实正是如此，因此我们认为这个例子满足最优性原理的要求。