新高考模式下遗传算法在排课问题中的应用
背景： 随着新高考改革在各个省份的推行，提出了“3+3模式”，即高中阶段的学生，不再区分文理科目，学生可以自主的从政治、历史、地理、物理、化学、生物和技术这7门课程里任选3门作为高考的考试科目。

  学校将班级分为行政班与教学班两类，行政班则于传统教学模式的班级相同，教学班是为不同行政班学生上选修课程组成的临时班级。一个学生的课程由行政班课程和选修课程组成，行政班课程由其所在的行政班开设，教学班课程则需要不同的行政班学生走到特定教室上课，此种上课方式在本文中统称为“走班制”，本文重点讨论排课问题，走班制的分班策略不在这里进行讨论。
需要解决的问题：


硬约束

1.	学生上课不能冲突：即行政班与教学班课程上课时间不能重合

2.	教师上课不能冲突：教师不能在同时段给不同的班带课

3.	教室分配不能冲突：行政班在本班上课，主要针对教学班和特殊课程（如技术）不同班使用不能冲突，且不能超出教室容量上限。


软约束

1. 课程连堂：同一天同一个午别（上午/下午）一个班的n个相邻课安排为相同的科目

2. 上下午不能连续上课：以老师的角度观察，每天上午最后一节课和下午第一节不能同时有课


基于二维染色体的遗传算法解决排课问题
二维实数编码
  本文遗传算法的染色体由一个二维数组表示，其行数和列数分别代表班级总数和教学课时总数，染色体C++语言定义如下：
class individual
{
public:
    vector<vector<int>> chromo;      //二维编码
    double fitness;                  //适应度
    double cal_fitness;               //累积适应度，用于轮盘赌
    int generation;                  //进化代数
}


  每个单元格（基因）构成一个课程单元，课程单元记录了年级ID、班级ID、班级类型、课程ID、教室ID、教室容量、教师ID等信息，染色体和课程单元C++语言定义如下:
struct course_elem
{
    int grade_id;        //年级ID
    int class_id;        //班级ID
    int class_type;      //1-教学班，2-走班
    int course_id;       //课程ID
    int teacher_id;      //老师ID
    int room_id;        //教室ID
    int capacity;        //教室容量
    int period_B;		 //两节连堂数
    int period_C;		 //三节连堂数
};


  染色体中填充为每个单元格的序号，故算法使用二维实数编码方式，这样的编码方式则可以很好的将设计应用到时间维上，将时间维划分为几个区块，如上午、下午等，可以更好的实施课程对时间段的要求，假设一天为上午5节课、下午4节课、一周5天，如下表所示。





1
2
3
4
5
6
7
…
44
45




行政1班












行政2班












行政3班












…












行政N班












教学1班












教学2班












…












教学N班












适应度函数
$f_i$表示个体$i$的硬约束条件冲突数，个体在当前排课方案中每违背一次约束条件，$f_i$值就加1。$g_i$表示个体$i$软约束的冲突数。对于一个可行的排课方案，硬约束条件必须得到满足，而软约束条件可以满足，也可以不满足。因此硬约束的在适应度函数中所占权重要远大于软约束的权重。则适应度函数可以表示为：

$F_i = f_i^2 + g_i , i = 1,2,3......,popsize$
选择
轮盘赌，又称为比例选择方法，其基本思想是：各个个体被选中的概率与其适应度大小成正比。

计算每个个体的适应度F；
计算每个个体的遗传概率；

$P(x_i) =\frac  {f(x_i)} { \sum_{j=1}^Nf(x_j)}$
计算每个个体的累积概率；

$q_i= \sum_{j=1}^iP(x_j)$
在[0,1]区间内产生一个均匀分布的伪随机数r;
若r<q[1]，则选择个体1，否则，选择个体k，使得：q[k-1]<r≤q[k] 成立；
重复(4)、(5)共N次。

轮盘赌的特点是，数值大的扇区，其被选中的概率大。可以实现种群中个体被选中的概率与个体适应值成正比。

在遗传操作的过程中，适应度值大的个体有较大的几率被选中，适应度低的个体则可能被淘汰。在种群的进化中，这样的选择算法保留了适应度好的接近目标解的个体。
交叉
  交叉操作采用分块小基因交叉算法，即每个班的课程单元只能在相同的班级进行交叉操作，而不能跨班（行）进行交叉。例如两个个体进行交叉时，只能个体1的1班行基因与个体2的1班行基因进行交换。这样的操作不会破坏班级对课程和课时的要求。

  为保证交换后各班的基因（课程单元）不重复，使用TSP实数编码的染色体交叉方法。下面举例说明交叉运算的过程。

任意选择一对染色体i，j作为父代的个体1和父代个体2;
生成一个随机数p，与交叉概率 进行比较，若p小于 则进行交叉操作（3），否则直接将父代1与父代2直接复制到自带种群中；
随机产生两个随机数 与 ， 为该班基因编号的左边界， 为右边界。 与 中间的部分即为要交换的基因段。假设 =3， =5如下图所示。

父代个体1


2
-1
3
0
1
4
5
-2
-6
-7


父代个体2


0
1
3
2
5
7
-2
-1
-4
6


4. 将两个个体中选出的基因段进行交换，交换后父代个体1中编号2与编号5的基因重复，父代个体2中编号为0与1的基因重复。为保证控制每个班的课程课时，必须保证每个班的基因段编号不重复，可将父代个体1与2中的未选择部分的重复基因进行交换。
 
父代个体1


0
-1
3
2
5
4
1
-2
-6
-7


父代个体2


2
5
3
0
1
7
-2
-1
4
6


变异
变异的过程是针对每个染色体个体内部的，为保证每个班级的既定的课程课时所以同交叉相同，变异操作限制在每个班级的基因段中。下图是变异前的染色体块，生成一个随机数p，与变异概率$p_m$比较，若p<$p_m$则对该染色体个体进行变异操作。
 
变异前染色体块


24
-1
25
23
20
24
22
-2
-3
21


随机产生两个随机数 与 ，分别表示待交换染色体段的位置信息，设 =4， =8，交换结果如下图所示
 
变异后染色体块


24
-1
25
-2
20
24
22
23
-3
21


算法流程

软硬约束冲突检测
代码皆为matlab伪代码

检测学生上课冲突

算法 1: 检测学生上课冲突
输入:
	stu(学生选课信息);
	stu_num：学生人数
	popsize：种群大小；
	length：个体一周的课时数；
	Adm_num：行政班数量；
	Edu_num：教学班数量；
输出:
	Stu_conflict:学生上课冲突数;
t←1;
while (t < popsize) do
	for i=1 to stu_num do
		得到学生教学班班号Edu_ClassCode
		得到学生教学班班号Adm_ClassCode
		for j=1 to Edu_num do
			   if(教学班班号 == ClassCode) then
			       for k=1 to Adm_num do
			          if(行政班班号 == Adm_ClassCode) then
			               判断该列对应行政班的课程单元编号是否为负
			               if(课程单元编号 > -1)
			                        Stu_conflict++;
							end if;
			            end if;
						 k←k+1;
				   end for;
			    end if;
			j←j+1;
		end for;
		i←i+1;
	end for;
	t←t+1;
end while.



教师上课冲突

算法 2: 教师上课冲突
输入:
	Individual(个体信息)；
	popsize：种群大小；
	length：个体一周的课时数；
	All_num：全部班数量；
输出:
	Tesc_conflict: 教师上课冲突数;
t←1;
while (t < popsize) do
	for i=1 to length do
		for j=1 to All_num do
			将所有的班级及其对应的课程ID存入新的二维矩阵record中
			j←j+1;
		end for;
		将每个record的重复内容进行统计并赋值给Num
		Tesc_conflict = Tesc_conflict + Num
		i←i+1;
	end for;
	t←t+1;
end while.



教室使用冲突

输入:
	Individual(个体信息)；
	popsize：种群大小；
	length：个体一周的课时数；
	All_num：全部班数量；
输出:
	Room_conflict: 教室使用冲突数;
t←1;
while (t < popsize) do
	for i=1 to length do
		for j=1 to All_num do
			将所有的班级及其对应的教室ID存入新的二维矩阵record中
			j←j+1;
		end for;
		 将每个record的重复内容进行统计并赋值给Num
		 Room_conflict = Tesc_conflict + Num
		i←i+1;
	end for;
	t←t+1;
end while.



连堂设置冲突

算法 4: 连堂设置冲突
输入:
	Individual(个体信息)；
	popsize：种群大小；
	Course_num：每个行政班包含的课程数量；
	Edu_num：教学班数量；
	Period_B：该课既定的二连堂数
	Period_C：该课既定的三连堂数
输出:
	Con_conflict: 连堂冲突数;
t←1;
while (t < popsize) do
	for i=1 to Edu_num do
		for j=1 to Course_num do
			times←1;
			p1←0;
			p2←0;
			period_Btimes←0;
			period_Ctimes←0;
			获取当前课程courseID
			        for k=1 to length do
			            if(course_id == courseID) then
			                if(times == 1)
			                   p1 = j; 
			                end if;
			                times←times+1;
			            else
			               if(times >1)
			                  p2=j;
			                  if(p2 – p1 >2)
			                     period_Btimes++;
			                  else if(p2-p1 > 2)
			                     period_Ctimes++;
			                  end if;
			                times =1;
			               end if;
			            end if;
			       k←k+1;
			end for;
			j←j+1;
			con_conflict +=abs(Period_B - period_Btimes)+abs(Period_B - period_Btimes);
		end for;
		i←i+1;
	end for;
	t←t+1;
end while.



上下午排课冲突

输入:
	Individual(个体信息)；
	popsize：种群大小；
	Edu_num：教学班数量；
	Day_num：一周需要上课的天数；
	Up_num：上午需要上课数；
	Down_num：下午需要上课数；
输出:
	Uad_conflict: 上下午排课冲突数;
t←1;
while (t < popsize) do
	for i=1 to Edu_num do
		for j=1 to Day_num do
			for k=1 to Up_num do
			   获得上午当前的课程upcourse_id;
			   for m=1 to Down_num do
			      获得下午当前的课程downcourse_id;
			       if(upcourse_id == downcourse_id) then
			           Uad_num++;
			       end if;
			      m←m+1;
			    end for;
			     k←k+1;
			     end for;
			j←j+1;
		end for;
		i←i+1;
	end for;
	t←t+1;
end while.


结果分析

二元锦标赛与轮盘赌选择对比

   二元锦标赛每次随机选择2个个体（放回的采样），从种群中随机选择2个个体，根据适应度值，选择适应度值最好的个体进入下一代种群。这使得适应值好的个体有更大的“生存机会”，而适应度差的被选中的机会很小，这样很容易产生超级个体，从而收敛速度比较快。

   轮盘赌选择利用各个个体适应度所占的比例大小决定其子孙保留的可能性，为了选择子代个体，需要进行多轮选择，每一轮产生一个[0,1]均匀随机数，将该随机数作为选择指针来确定被选个体。由于随机操作的原因，这种选择方法的选择误差也比较大，有时连适应度较高的个体也选择不上。

   本文使用了四个数据集基于遗传算法的排课问题，分别使用二元锦标赛和轮盘赌选择法进行对比，如图4.1所示，其中蓝色折线为轮盘赌选择算子，红色折线为二元锦标赛选择算子。







   可以看出二元锦标赛选择法是呈收敛趋势，轮盘赌选择算法效果较差，不呈现出收敛的趋势。其中该方法不能全局收敛的主要原因是由于存在统计误差，依据产生的随机数进行选择，有可能会出现不正确反应个体适应度的选择，可能导致适应度高的个体也被淘汰掉。

   Rudolph已经采用有限马尔可夫链理论证明了仅采用交叉、变异和选择(轮盘赌选择法)三个遗传算子的标准遗传算法(Canonical Genetic Algorithm CGA)，不能收敛到全局最优值。由此需要算法需要引入一个重要的收敛策略-精英保留策略。

2. 个体精英保留策略与群体精英保留策略对比

  个体精英保留策略是将父代中适应度最好的个体，不经过变异与交叉操作直接进入子代中，替换子代中适应度最差的个体。

  群体精英保留策略是将父代种群和子代种群合并后，选择其中最优的N个（种群大小）个体构成下一代个体。下图为四个数据集基于轮盘赌选择方法采用不同的保留策略的测试结果。






  在这里插入图片描述图中蓝色折线为个体精英保留策略，红色折线为种群精英保留策略，可以看出，种群的精英保留策略收敛速度更快，相比个体精英策略更易于收敛到全局最优。

hello，大家好。各位可点击此处，访问公众号官方店铺。谨防上当受骗，感谢各位支持！
在MATLAB数学建模教学（八） | 粒子群优化（PSO）算法真的过时了吗？这篇推文中一位粉丝留言说希望讲解一下动态多目标旅行商问题。
今天我们满足这位粉丝的要求，来好好聊一聊动态多目标旅行商问题（Dynamic Multi-Object Traveling Salesman Problem，DMOTSP），后续统一简称为DMOTSP。
本篇推文主要从以下几个方面展开：
01DMOTSP的问题描述
02Inver-Over算法
03 参考文献
01 |DMOTSP的问题描述​
在讲解DMOTSP之前，我想各位一定都知道TSP，TSP就是找出一条路线，使得该条路线的成本最小。DMOTSP实际上可以将TSP前面的两个定语提出来，即动态和多目标。
动态体现在城市的状态可能会在下一时刻发生以下三种变化：1）城市消失；2）新的城市出现；3）城市的位置改变。
多目标体现在DMPTSP的目标可能存在多个，即可能包括路程最短、风险最小等。
接下来给出DMOTSP的定义：DMOTSP的代价矩阵是随着时间变化的。假设有m个目标，他们的m个代价矩阵的元素和阶数是时间t的函数，一般可描述如下：
其中 
 是目标k在时刻t城市i到城市j的
代价，  
 是在时刻t城市的
数目。
假设给定 
 个城市及城市之间的代价矩阵
和路径
，那么
目标k在时刻t的适应度函数为：
 ，其中
。
给定m个目标的
，对于路径
，若不存在其它路径 
 ，使得 
 ，
其中至少一个不等式严格成立，那么 
 为在时刻t的
Pareto最优解。
 组成的集合
称为在时刻t的
Pareto最优解集。
m维目标向量 
 ， 
 ，它们在m维目标空间描绘出的图形
称为在时刻t的
Pareto最优前沿。
综上所述，DMOTSP可描述如下：在时刻t，给定
个城市及城市之间的代价矩阵 
，求Pareto最优解集
及其Pareto最优前沿
 。
对于Pareto解还比较模糊的小伙伴，可以查看多目标优化 | 基于NSGA-II的多目标0-1背包问题求解（附matlab代码）这篇推文进行学习。
Pareto最优解：对于多目标优化问题，通常存在一个解集，这些解之间就全体目标函数而言是无法比较优劣的，其特点是:无法在改进任何目标函数的同时不削弱至少一个其他目标函数。这种解称作非支配解或Pareto最优解。
Pareto最优前沿：对于组成Pareto最优解集的所有Pareto最优解，其对应目标空间中的目标矢量所构成的曲面称作Pareto最优前沿。
​02 | Inver-Over算法
在介绍求解DMOTSP问题的DMOInver-Over算法前，先介绍Inver-Over算子，作为预备知识。
下面通过一个例子详细讲解Inver-Over算子，假设
 ，当前个体为 
 。
假设从 
 随机移除的城市 c=5此时进入repeat循环：
第一次循环：
假设rand=0.005，则rand<=p1。
假设此时从
中剩余的城市（即1,2,3,4,6,7,8,9）中随机选择的城市为 
  。
此时 
 中城市5的下一个城市不是城市8，因此不能跳出repeat循环。
倒置中城市5至城市8之间的排序序列，此时 
更新c=8。
第二次循环：
​假设rand=0.5，则rand>p1。
假设此时从种群P中随机选择出的个体为 
此时将
中城市8的紧邻的下一个城市7赋值给
，即 
 。
此时 
 中城市8的下一个城市是城市7，因此跳出repeat循环。
跳出repeat循环后：
如果当前 
 的适应度值大于
的适应度值，则 
 。
03 |参考文献
[1] 杨鸣. 动态多目标 TSP 演化算法研究[D]. 中国地质大学, 2008.
[2] Tao G, Michalewicz Z. Inver-over operator for the TSP[C]//International Conference on Parallel Problem Solving from Nature. Springer, Berlin, Heidelberg, 1998: 803-812.
这期就讲到这里，下期会在Inver-Over算法的基础上讲解求解DMOTSP的DMOInver-Over算法，然后以一个实际例子来详细阐述DMOInver-Over算法的求解过程，我们下期见。
各位小伙伴可在留言板留言，未来我们讲解的具体内容由你做主。如果可以的话，可以把希望讲解的文献也在留言板上写出来。
留言板​mp.weixin.qq.com
更多精彩尽在公众号：优化算法交流地
往期推荐
多目标优化 | 基于NSGA-II的多目标0-1背包问题求解（附matlab代码）​mp.weixin.qq.com多目标优化 | NSGA-II进阶教程（全网首个三目标优化教程）​mp.weixin.qq.comMATLAB数学建模（五）| 还在为不会写多目标优化算法代码而发愁吗？教你快速上手gamultiobj工具箱！​mp.weixin.qq.comNSGA-II多目标优化算法讲解（附MATLAB代码）​mp.weixin.qq.com多目标优化 | NSGA-II​mp.weixin.qq.com
知乎 | bilibili：随心390

动态规划是算法中的难点与重点，面试的时候应该也会经常遇到。动态规划是运筹学的一个分支，是求解决策过程最优化的教学问题，其处理对象是多阶段决策问题。这种问题一般可以分解成为若干个相互联系的阶段，在每一个阶段都要做出决策，形成一个决策序列，该决策序列也成为一个策略。对于每一个决策序列，可以在满足问题的约束条件下用一个数值函数(即目标函数)衡量该策略的优劣。多阶段决策问题的最优化目标是获取导致问题最优值的最优决策序列，即得到最优解。

最优性原理

假设为了解决某一多阶段决策过程中的优化问题，需要依次作出n个决策，如果这个决策序列是最优的，对于任何一个整数k，，无论前面k个决策是怎样的，以后的最优决策只取决于由前面决策所确定的当前状态，即以后的决策序列也是最优的。

最优性原理体现为问题的最优子结构特性，最优子结构特性是动态规划求解问题的必要条件。

个人觉得递推算法的思想是动态规划算法的第一步。

动态规划实施步骤

1. 把所求最优化问题分成若干个阶段，找出最优解的性质，并刻划其结构特性。

2. 将问题各个阶段时所处不同的状态表示出来，确定各个阶段状态之间的递推关系，并确定初始条件。

3. 应用递推求解最优值

4. 根据计算最优值时所得到的信息，构造最优解，构造最优解就是具体求出最优决策序列。

示例

1. 插入乘号问题，n在一个由n个数字组成的数字串中插入r个乘号(1≤r<n)，将它分成r+1个整数，找出一种乘号的插入方法，使得这r+1个整数的乘积最大。例如：在数字串847313926中插入5个乘号，分为6个整数相乘，使乘积最大的最优解为:



该最优解包含了以下子问题的最优解：

1) 在84731中插入2个乘号使得乘积最大为：8*2*731;

2) 在7313中插入1个乘号使得乘积最大为：731*3；

3) 在3926中插入2个乘号使乘积最大为：3*92*6；

4) 在4731392中插入3个乘号使得乘积最大为：4*731*3*92 

第一步：首先建立递推关系，设表示在前i位数中插入k个乘号所得乘积的最大值，表示从第i个数字到第j个数字所组成的j-i-1(i<=j)位整数值。

一般地，为了求取，考察数字串的前i个数字，设前j(k<=j<i)个数字中已经插入k-1个乘号的基础上，在第j个数字后插入第k个乘号，显然此时的最大乘积为。于是可以得到以下递推关系式：



前j个数字没有插入乘号时的值显然为前j个数字组成的整数，因而得到边界值：，其中。

第二步：递推设计最优值，以下为实现上述问题的python代码：

temp = str(input())  #输入数字串
r = int(input())       #输入要插入多少个乘号
#对数字串temp进行分离
number = []
length = len(temp)
for i in range(length):
    number.append(int(temp[i]))
d = 0
f = [[0 for i in range(r+1)] for j in range(length+1)]
#初始化边界条件
for j in range(1,length+1):
    d = d*10+number[j-1]
    f[j][0] = d
for k in range(1,r+1):
    for i in range(k+1,length+1):
        for j in range(k,i):
            d = 0
            for u in range(j+1,i+1):
                d = d*10+number[u-1]
            if(f[i][k]<f[j][k-1]*d):
                f[i][k] = f[j][k-1]*d
print("最优解为:",f[length][r])

2. 最长非降子序列，由n个正整数组成的序列，从该序列中删除若干个整数，使剩下的整数组成非降子序列，求最长的非降子序列。例如，由12个正整数组成的序列为：



请在序列中删除若干项，使得剩下的项为非降(即后面的项不小于前面的项)序列，非降序列最多为多少项：

第一步，建立递推关系，设序列的各项为a[1],a[2],...,a[n]，对每个整数操作作为一个阶段，共为n个阶段。设置b数组，b[i]表示序列的第i个数(包含第i个数)到第n个数中的最长非降子序列的长度，i=1,2,...,n。对所有的i>j，比较当a[j]>=a[i]时b[j]的最大值，显然b[i]为这一项最大值加1，表示加上a[i]本省这一项。因而有递推关系：，其中。边界条件b[n]=1。

第二步：递推计算最优值，以下是上述问题的python代码实现：

number = list(map(int,input().split(',')))
length = len(number)
b = [0 for i in range(length)]

b[length-1] = 1

for i in range(length-1,-1,-1):
    maxnumber = 0
    for j in range(i+1,length):
        if(number[i]<=number[j] and b[j]>maxnumber):
            maxnumber = b[j]
        b[i] = maxnumber+1
print(max(b))

3. 矩阵中的最大路径，在一个给定的n行m列矩阵中，从矩阵的左上角走到右下角，路径中每一步能往右、往下走到相邻格子，不能斜着走，也不能走出矩阵。试着在所有路径中搜索路径上各数和最大的最大路径。例如，所示10x8矩阵中，如何确定最大路径？



 设第(i,j)表示第i行第j列格，数组a(i,j)存储该格(i,j)中的数字；数组b(i,j)为(i,j)至矩阵右下角(n,m)路径的最大数字和；数组c(i,j)存储(i,j)下步向标：向下为“D”,向右为“R”；数组d(i,j)从格(i,j)至右下角(n,m)不同最大路径的条数。显然，最优路径的数字和为b(1,1)。

第一步，建立递推关系，b(i,j)与c(i,j)（i=n,...,2,1;j=m,...,2,1）的值由整数b(i+1,j)与整数b(i,j+1)的大小决定：



这样反推所得到的b(1,1)即表示所求的最大路径数之和。我们可以看到，并非直接计算从左上角第一个格子到右下角最后一个格子的路径，而是从右下角最后一个格子反向推导到左上角第一个格子的路径。

我们看以下数组d的递推关系：



 数组d(i,j)从格(i,j)至右下角(n,m)不同最大路径的条数。

第二步，确定边界条件，最后一行和最后一列只有一个出口，最后一行只能向右边走，最后一列只能向下面走，现在由b[n][m]=a[n][m]开始：



产生最优路径：路径左上角(i=1,j=1)开始，至右下角(i=n,j=m)结束，中间各点通过循环while(i+j<m+n)实现。

第三步：递推计算最优值，以下是上述问题的python代码实现：

a = [[2,3,4,2,1,1,4,5],
     [2,1,3,2,5,2,3,1],
     [5,4,5,5,1,1,3,5],
     [4,1,4,4,2,2,1,3],
     [5,4,4,2,4,5,5,4],
     [5,4,3,4,1,1,1,2],
     [3,4,3,3,1,4,1,2],
     [5,2,3,5,4,3,2,2],
     [3,3,4,2,2,5,4,5],
     [5,5,4,2,4,5,3,4]]
n = len(a)  #行
m = len(a[0]) #列
b = [[0 for i in range(m)] for j in range(n)]
c = [[0 for i in range(m)] for j in range(n)]
d = [[0 for i in range(m)] for j in range(n)]
#确定边界条件
b[n-1][m-1] = a[n-1][m-1]
for j in range(m-2,-1,-1):
    b[n-1][j] = a[n-1][j]+b[n-1][j+1]
    c[n-1][j] = "R"
    d[n-1][j] = 1
for i in range(n-2,-1,-1):
    b[i][m-1] = a[i][m-1]+b[i+1][m-1]
    c[i][m-1] = "D"
    d[i][m-1] = 1
#建立递推关系
for i in range(n-2,-1,-1):
    for j in range(m-2,-1,-1):
        if(b[i+1][j]>b[i][j+1]):
            b[i][j] = a[i][j]+b[i+1][j]
            c[i][j] = "D"
            d[i][j] = d[i+1][j]
        if (b[i + 1][j] == b[i][j + 1]):
            b[i][j] = a[i][j] + b[i + 1][j]
            c[i][j] = "D"
            d[i][j] = d[i + 1][j] + d[i][j+1]
        if (b[i + 1][j] < b[i][j + 1]):
            b[i][j] = a[i][j] + b[i][j+1]
            c[i][j] = "R"
            d[i][j] = d[i][j + 1]
print(b[0][0])

 总结：动态规划根据不同阶段之间的状态转移，通过应用递推求得问题的最优值。这里，注意不能把动态规划与递推两种算法相混淆，不要把递推当成是动态规划，也不要把动态规划当成递推。多刷题有利于熟悉算法。