计算与人工智能概论-问题求解、科学计算与AI应用方法 课件 第9章 算法

计算与人工智能概论问题求解、科学计算与AI应用方法第9章算法信息科学与工程学院穷举算法

分治算法

动态规划（递归）

动态规划（递推）

目录穷举算法任务描述：数字三角形问题数字三角形：包含多层数字的三角形，每一层比上一层增加一个数字，假设所有的数字均大于0。路径：从最上层的数字出发往下走，每次只能往左下或右下走，走到最底层时，形成一条完整的路径。最大“路径和”：对所有可能的路径求出“路径和”，最大者为最大“路径和”。图c的路径和为30，是所有“路径和”中最大者。路径和：路径上的所有数字之和。图b所示路径的”路径和”为7+8+1+7+2=25。这个问题怎么求解呢?穷举算法相关知识：求解数字三角问题的基本思路数字三角形问题优化目标：找出路径和最大的路径。最优化问题：在给定的约束条件下,求解最优方案使得目标最大化或最小化的问题。哪个路径和更大？比一比【解决方案】枚举所有可能的路径并计算路径和，找出最大路径和。【穷举算法】枚举所有可能解，计算每个解的结果，找出最优解（枚举-计算-验证）。穷举算法相关知识：什么是算法？算法是一个有穷规则的集合，它用规则规定了解决某一特定类型问题的运算序列，或者规定了任务执行或问题求解的一系列步骤。最早的算法：公元前3世纪，欧几里得《几何原本》，求最大公约数的辗转相除法如音乐乐谱、太极拳谱等都可看作广义的算法穷举算法相关知识：算法及其描述求“路径和”的算法Input:路径中数字构成的数组D=[d0,...,dn-1]；Output:数组D的n个数字之和；Step1.令一个变量sum的值为0，令一个变量i的值为0；Step2.将di累加到sum，并将i增加1；Step3.若i小于n转到Step2；否则输出sum，算法结束。算法的自然语言描述输入D=[7,8,1,7,2]初始状态sum=0,i=0第1次循环sum=7,i=1先将D[i]加到sum第2次循环sum=15,i=2再将i加1第3次循环sum=16,i=3第4次循环sum=23,i=4第5次循环sum=25,i=5(i等于n退出循环)算法的模拟执行穷举算法相关知识：算法的5个基本特征有穷性：一个算法在执行有穷步规则之后必须结束。确定性：算法的每一个步骤必须要确切地定义，不得有歧义性。输入：算法有零个或多个的输入。输出：算法有一个或多个的输出/结果，即与输入有某个特定关系的量。能行性：算法中有待执行的运算和操作必须是相当基本的(可以由机器自动完成)，并能在有限时间内完成。求“路径和”的算法Input:路径中数字构成的数组D=[d0,...,dn-1]；Output:数组D的n个数字之和；Step1.令一个变量sum的值为0，令一个变量i的值为1；Step2.将Di累加到sum，并将i增加1；Step3.若i小于n转到Step2；否则输出sum，算法结束。基本运算：除法、赋值、逻辑判断典型的“重复/循环”与“迭代”穷举算法相关知识：数学建模数学建模是用数学语言描述实际现象的过程，即建立数学模型的过程。数学模型是对实际问题的一种数学表述，是对部分现实世界为某种目的而进行的一个抽象与简化的数学结构。l输入：一个二维向量A={{a00},{a10,a11},...,{an-10,...,an-1n-1}}，

其中的元素aij>0,0<=i<=n-1,0<=j<=i；l输出：对于路径：

输出其“路径和”：l约束条件：路径P中|ji-ji-1|=0或1，i=1,2,...,n-1；l优化目标：“路径和”S最大。数字三角形问题的数学模型：穷举算法相关知识：什么是数据结构数据结构是数据的逻辑结构、存储结构及其操作的总称，它提供了问题求解/算法的数据操纵机制。(数据的)逻辑结构(数据的)存储结构操作反映逻辑语义关系为便于计算系统处理数据的逻辑结构描述数据之间的逻辑语意关系；数据的存储结构是在反映数据逻辑关系的原则下，便于计算系统处理的物理结构穷举算法相关知识：数据的逻辑结构与存储结构线性表：n（n≥0）个具有相同特性的数据节点构成的有限序列

树：一种逻辑上表现为一颗倒挂的树的结构

图：一种由节点和连接节点的边构成的结构

顺序存储：数据在物理结构上是连续的，例如C语言数组。链式存储：数据在物理结构上是非连续的，例如链表。数字三角形用什么数据结构?三种逻辑结构：线性表、树、图。两种存储结构：顺序存储、链式存储。穷举算法相关知识：算法的基本控制结构算法的控制结构描述了算法的操作步骤，控制结构的设计反映了算法的思想顺序结构：“执行A，然后执行B”，是按顺序执行一条条规则或语句的一种结构。分支结构：“如果Q成立，那么执行A，否则执行B”，Q是某些逻辑条件，即按条件判断结果决定执行哪些规则或语句的一种结构。循环结构：控制规则或语句多次执行的一种结构---迭代(iteration)循环结构又分为有界循环结构和条件循环结构。有界循环：“重复N次执行A”，其中N是一个整数。条件循环：某些时候称为无界循环，“重复执行A直到条件Q成立”或“当Q成立时反复执行A”，其中Q是条件。穷举算法相关知识：可能解与解空间可能解：解的取值空间中任何可能的一个值。数字三角形问题的可能解：

一条合法路径上的数字形成的数字序列解空间：由问题的所有可能解构成的集合。数字三角形问题的解空间：

所有合法路径构成的集合问题求解的过程：在解空间中搜索符合问题约束以及优化目标的解。穷举算法相关知识：穷举算法及其特点穷举算法：最基本的算法，基本思想是枚举出问题的所有可能解，然后逐一判断这些解是否满足问题的条件，从而找到符合条件的解。即：枚举-计算-验证。枚举：对解空间进行遍历，逐一枚举所有的可能解。计算：计算可能解的结果。验证：验证可能解是否符合约束条件和优化目标。穷举算法适用于问题的解空间有限且规模较小的情况。穷举算法相关知识：算法的描述方法算法描述的3种方法：自然语言描述法、流程图、伪代码求数字序列之和的算法（自然语言描述）Input:n个具有先后次序的数字序列D=[d1,d2,...,dn]；Output:序列D的n个数字之和；Step1.初始化变量sum的值为0，变量i的值为1；Step2.将di加到sum上，并将i增加1；Step3.若i小于等于n则跳转到Step2执行；否则输出sum，算法结束。穷举算法相关知识：算法的时间复杂度单位执行时间：执行一次基本运算所需的平均时间，用来做基本单位时间复杂度:如果一个问题的规模是n，求解这一问题的某一算法所需要的时间为T(n)，它是n的某一函数，则T(n)称为这一算法的“时间复杂度”。基本参数n——问题规模，表明输入数据的规模大小把复杂性或运行时间表达为n的函数。算法获得结果需要多长时间?时间复杂度时间复杂度描述算法随输入数据规模增长时，运算次数的增长趋势。算法的时间复杂度与计算机的性能无关时间复杂度是衡量算法本身求解问题效率的一种度量标准。穷举算法相关知识：时间复杂度分析示例时间复杂度描述算法随输入数据规模增长时，运算次数的增长趋势。此处是线性增长趋势。求数字序列之和的算法Input:n个具有先后次序的数字序列D=[d1,d2,...,dn]；Output:序列D的n个数字之和；Step1.初始化变量sum的值为0，变量i的值为1；Step2.将di加到sum上，并将i增加1；Step3.若i小于等于n则跳转到Step2执行；否则输出sum，算法结束。Step1：2条赋值语句；Step2：2条加法语句（重复n次）；Step3：执行1条判断语句（重复n次），算法结束前，执行1条输出语句T(n)=2+2n+n+1=3n+3穷举算法相关知识：渐进时间复杂度与大O标记法“大O记法”：渐进时间复杂度

n越大，低阶项和系数的影响越小

去掉低阶项和系数，再用O进行标记

“O”表示量级(order)，允许使用“=”代替“≈”，如3n2+4n+1=Ο(n2)。O(f(n))T(n)=3n+3

=

O(n)求数字序列之和的算法Input:n个具有先后次序的数字序列D=[d1,d2,...,dn]；Output:序列D的n个数字之和；Step1.初始化变量sum的值为0，变量i的值为1；Step2.将di加到sum上，并将i增加1；Step3.若i小于等于n则跳转到Step2执行；否则输出sum，算法结束。穷举算法相关知识：不同的时间复杂度量级指数量级：O(bn),O(n!)多项式量级：O(1),O(logn),O(n),O(nlogn),O(nb)以1千万个单位时间为1秒时间复杂度问题规模nn=10n=100n=1000O(1)常数0.001毫秒0.001毫秒0.001毫秒O(logn)对数0.003毫秒0.006毫秒0.0096毫秒O(n)线性0.01毫秒0.1毫秒1毫秒O(nlogn)线性对数0.03毫秒0.66毫秒9.97毫秒O(n2)平方0.1毫秒10毫秒1秒O(2n)指数1毫秒4*1016年3.4*10287年O(n!)阶乘3.6秒2.9*10144年1.3*102555年穷举算法设计思路：（数字三角形问题）可能解的表达方法用0和1编码：

向左为0

向右为1从低位到高位排列，便于取出穷举算法设计思路：（数字三角形问题）解空间及其枚举方法0～2n-1-1，一个数字对应一个解；从0循环到2n-1-1，即可对解空间遍历穷举算法设计思路：（数字三角形问题）路径和计算求路径和的算法Input:代表数字三角形的大小为n*n的二维数组A[n][n]，代表路径的整数POutput:路径P的路径和sumStep1.初始化路径和sum的值为A[0][0]，令路径P的当前坐标(i,j)=(0,0)；Step2.计算P的下一个位置坐标：i=i+1，j=j+(P%2)Step3.令sum=sum+A[i][j]，P=P/2；Step4.若i<n-1，跳转到Step2；否则返回sum，算法结束。P%2的结果是为0表示向左转（列号j不变），为1表示向右转（列号j加1）穷举算法设计思路：（数字三角形问题）筛选/验证最大路径和筛选最大路径和算法（打擂台算法）Input:n层数字三角形Output:最大的路径和resStep1.初始化res值为0，i的值为0；Step2.计算第i条路径和sum；Step3.若sum>res，令res=sum；Step4.令i=i+1,若i<2n-1，跳转到Step2；否则返回res，算法结束。循环2n-1次枚举解空间，计算路径和，验证谁最大，此即穷举算法。枚举解空间循环2n-1次，路径和计算循环n次，时间复杂度：O(n2n)穷举算法代码实现#include<stdio.h>#include<math.h>intn;//数字三角形层数intA[100][100];//存储数字三角形的数组intmain(){freopen("in.txt","r",stdin);//将标准输入重定向到文件scanf("%d",&n);

//读取数字三角形层数for(inti=0;i<n;i++){//外循环，i为三角形的行号for(intj=0;j<=i;j++)scanf("%d",&A[i][j]);//内循环读取三角形的第i行，j为列号}intres=0;//最终结果，初值为0穷举算法代码实现（续）for(intP=0;P<pow(2,n-1);P++){//枚举解空间，P为路径intsum=A[0][0];//sum为P的路径和，初值为三角形顶部的数字intj=0;//j为列号intcode=P;//code为路径，将被移位修改for(inti=1;i<n;i++){//对路径code的每一位进行循环处理，i也是行号j+=(code%2);//根据路径的最低位调整列号sum+=A[i][j];//计算路径和：取出路径中当前位置的数字并累加到sumcode>>=1;//路径右移一位}if(sum>res)res=sum;//验证/筛选最大路径和}printf("%d\n",res);//输出最终结果return0;}穷举算法

分治算法

动态规划（递归）

动态规划（递推）

目录分治算法任务描述：数字三角形问题换一种解题思路：直接对路径进行枚举的穷举算法面临指数爆炸问题，即随着层数的增加，算法的时间复杂度呈指数增长。如何提高效率呢？可以换一种结题思路。有没有另外的求解方法?最大“路径和”：对所有可能的路径求出“路径和”，最大者为最大“路径和”。图c的路径和为30，是所有“路径和”中最大者。分治算法相关知识：基于问题分解的分治算法分解：将原问题分解为形式相同且规模更小的子问题，如果子问题还是难以求解就继续分解，直到子问题可以直接求解，可以直接求解的子问题被称为最小子问题。解决：利用定义或其他简单方法直接求解最小子问题的解。合并：按原问题的要求，将子问题的解以计算、选择等方法逐层合并，构造出原问题的解。分治算法：将问题向下分解为形式相同的更小的子问题，子问题一直分解下去，直到能直接求解（解决），然后向上将子问题的解合并为更大规模问题的解。分治算法相关知识：斐波那契数列问题斐波那契数列（Fibonaccisequence），又称黄金分割数列，因意大利的数学家莱昂纳多·斐波那契在1202年的《计算之书》以兔子繁殖为例子而引入，故又称为“兔子数列”。兔子在出生两个月后就具有生殖能力，设有一对兔子每个月都生一对兔子，生出来的兔子在出生两个月之后，每个月也可以生一对兔子。那么，从一对小兔开始，满一年可繁殖多少对兔子？分治算法相关知识：斐波那契数列问题的问题分解形式相同的子问题：参数个数相同（这里都是1个），功能相同（都是求斐波那契数）。规模更小的子问题：参数i越小问题规模越小。分治算法：将f(i)向下分解为形式相同的更小的子问题f(i-1)和f(i-2)，子问题一直分解下去，直到能直接求解（f(0)和f(1)都是1），然后向上将子问题的解合并为更大规模问题的解（f(i-1)+f(i-2)得到f(i)）。递归公式：分治算法相关知识：斐波那契数列问题的代码实现#include<stdio.h>intf(inti){if(i==0||i==1)return1;//解决最小子问题elsereturnf(i-1)+f(i-2);//分解、合并（递归）}intmain(){intn;scanf("%d",&n);//读取nprintf("%d\n",f(n));//输出最终结果return0;}分治算法相关知识：分治算法的一般流程Step1.将原问题的求解设计为一个函数f（设参数表为arg，返回值为r），其中参数表指定了问题的规模。原问题调用方式为f(arg_ori)，其中arg_ori为参数表；Step2.根据参数判断是否为最小子问题，若为最小子问题，直接求出并返回结果，回到递归函数的上一层；Step3.若不是最小子问题，对问题进行分解，用合适的参数表达子问题，并递归调用之，子问题记为f(arg_sub)，其中，arg_sub为子问题的参数表，注意分解后的子问题可能有多个；Step4.使用计算或选择等方法，利用子问题的解构造出上一级问题的解并将之返回。分治算法设计思路：数字三角形问题的分解与合并集合P1，最大路径7-3-8-7-5，路径和30集合P2，最大路径7-8-1-7-5，路径和28令所有路径集合P=P1+P2,则最大路径和max(P)=max(max(P1),max(P2))分治算法设计思路：数字三角形问题的分解与合并（续）max(P1)=7+max(P1’),max(P2)=7+max(P2’)分治算法设计思路：数字三角形问题的分解与合并（续）P1’和P2’分别对应一个较小的三角形（子问题），其顶点都在第二层。一个数字三角形可用其顶点位置坐标来标识。P的顶点坐标(0,0)，P1’的顶点坐标(1,0)，P2’的顶点坐标(1,1)。分治算法设计思路：数字三角形问题的最小子问题只有一个数字的三角形是最小子问题，其最大路径和是该数字本身。分治算法设计思路：数字三角形问题的递归公式分解后的两个较小的三角形的最大路径和分别为f(1,0)和f(1,1)，且：f(0,0)=A[0][0]+max(f(1,0),f(1,1))以坐标（i,j）上的数字为顶点的三角形，定义其最大路径和为f(i,j)。最初的三角形最大路径和为f(0,0)。分治算法设计思路：数字三角形问题的分治算法

数字三角形问题的分治算法Input:代表数字三角形的大小为n*n的二维数组A[n][n]Output:数字三角形的最大路径和Step1.定义递归函数f，其参数i和j为数字三角形的顶点坐标；Step2.若i等于n-1，函数退出并返回A[i][j]；Step3.i小于n-1时，分别以(i+1,j)和(i+1,j+1)为参数递归调用此函数，两个递归调用的返回值相加之后再加上A[i][j]，函数退出并返回该结果，函数定义结束；Step4.以参数（0,0）调用递归函数f，即f(0,0)，返回值为最大路径和；Step5.输出函数的返回值。分治算法设计思路：数字三角形问题分治算法的时间复杂度分析T(n)=2*(1+2+…+2n-2)=2*(2n-1-1）=O(2n)分治算法代码实现#include<stdio.h>#definemax(a,b)((a)>(b)?(a):(b))intn;//数字三角形层数intA[100][100];//存储数字三角形的数组intf(inti,intj)//递归函数{if(i==n-1)returnA[i][j];//最小子问题else{inta=f(i+1,j);//向下移动intb=f(i+1,j+1);//向右下移动returnA[i][j]+max(a,b);//问题分解与合并}}intmain(){freopen("30.txt","r",stdin);//将标准输入重定向到文件scanf("%d",&n);//读取数字三角形层数for(inti=0;i<n;i++){for(intj=0;j<=i;j++)scanf("%d",&A[i][j]);}printf("%d\n",f(0,0));//输出最终结果return0;}传说古老印度的一个圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必在大片上面。当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，梵塔、庙宇和众生都将同归于尽。我们的任务是，编写程序，输出将所有的金片从A移动到C的详细步骤。练习：汉诺塔问题原问题：将n个金片从A移动到C（借助B）。分解：将上面的n-1个金片从A移动到B（借助C）；将最下面的金片直接从A移动到C；将n-1个金片从B移动到C（借助A）。合并：上述3个动作的结果一起构成原问题的解。最小问题：当移动的金片只有一个时，可直接移动。解题思路穷举算法

分治算法

动态规划（递归）

动态规划（递推）

目录动态规划（递归）任务描述：数字三角形问题指数量级的算法：分治算法求解数字三角形问题的算法拥有指数量级的时间复杂度，效率依然很低。如何进一步提高效率?最大“路径和”：对所有可能的路径求出“路径和”，最大者为最大“路径和”。图c的路径和为30，是所有“路径和”中最大者。动态规划（递归）相关知识：消除算法的无效计算1.消除不必要遍历（剪枝）2.消除重复计算3.优化解空间搜索策略三种提高算法效率的手段动态规划（递归）相关知识：重叠子问题斐波那契数列的重叠子问题：f(3)调用2次，f(2)调用3次。动态规划（递归）相关知识：动态规划将已经求解子问题的解保存到一张表格中，遇到已经求解的重叠子问题时，从表格中直接取出该问题的解。用来保存子问题的解的表格就是动态规划（简称DP）。动态规划（递归）相关知识：状态与状态值状态：代表子问题的一组参数。例如斐波那契数列，非负整数i=0、1、2......都是问题的有效状态。状态值：一个状态对应一个或多个子问题，状态值就是这个状态所对应的子问题的解。例如，斐波那契数列中状态4的状态值是f(4)=5。初始状态：最小子问题对应的状态被称为初始状态，初始状态也称为边界状态，是递归函数的出口，例如斐波那契数列问题的初始状态为0和1。状态空间：所有状态构成的集合称为状态空间。例如斐波那契数列问题的状态空间为{0,1,2...n}。动态规划（递归）相关知识：状态转移方程状态转移：确定问题的状态以及状态值的求解方法后，动态规划算法需要在不同状态之间建立联系，即通过一个或一些状态值，计算出另一个状态值，这种推导方法被称为状态转移。状态转移方程：用于描述状态转移的方程被称为状态转移方程，状态转移方程定义了从一个或多个状态转移到另一个状态的方法，同时，状态转移方程需要定义初始状态值的求解方法。状态转移方程就是递归公式的另一个名称。斐波那契数列的状态转移方程：动态规划（递归）相关知识：动态规划（DP）表格的定义DP表格的大小：表格能容纳所有状态值，即表格的大小与状态空间大小一致。DP表格的维度：表格的维度与状态参数的个数一致。DP表格元素的类型：元素类型与状态值一致。例：斐波那契数列的状态参数只有1个，状态空间大小是n，状态值的类型是longlong，因此定义大小为n的一维数组longlongDP[n]。动态规划（递归）相关知识：为分治算法添加DP表格参数->状态：递归函数f(i1,i2,……ik,P)，其中i1,i2,……ik是与子问题规模相关的参数，P是其他参数集合，则i1,i2,……ik可认为是标识该子问题的状态。函数入口处检查DP表格：在递归函数最开始的地方，以参数表中代表状态的信息为索引，到DP表格中进行检索，若其值不是最初的初始值，表明该状态已经计算过，函数直接返回这个状态值。状态值保存到DP表格：递归函数在返回之前，同样以参数表中代表状态的信息为索引，将状态值保存到动态规划表格中，然后函数返回状态值。动态规划（递归）相关知识：使用DP生成斐波那契数列的代码实现#include<stdio.h>longlongDP[10001];longlongf(inti){

if(DP[i]!=-1)returnDP[i];//已计算子问题longlongres;if(i==0||i==1)res=1;//解决最小子问题elseres=f(i-1)+f(i-2);//分解、合并

DP[i]=res;//保存计算结果returnres;}intmain(){intn;scanf("%d",&n);//读取问题规模nfor(inti=0;i<=n;i++)DP[i]=-1;//数组元素赋初值printf("%lld\n",f(n));//输出最终结果return0;}动态规划（递归）设计思路：重叠子问题分析动态规划（递归）设计思路：数字三角形问题的状态、状态值与状态转移方程状态：三角形的顶点可以决定一个三角形，可使用三角形的顶点坐标作为子问题的状态，例如，原问题中三角形顶点坐标为(0,0)，因此其状态为(0,0)。状态值：对于任意状态，其状态值为对应三角形的最大路径和。数字三角形问题的状态转移方程（递归公式）：动态规划（递归）设计思路：基于递归的动态规划算法的自然语言描述

数字三角形问题的动态规划算法（基于递归）Input:代表数字三角形的大小为n*n的二维数组A[n][n]Output:数字三角形的最大路径和Step1.定义动态规划表格DP[n][n]，元素初值都为-1；Step2.定义递归函数f，其参数i和j为数字三角形的顶点坐标；Step3.若DP[i][j]不等于-1，函数退出并返回DP[i][j]；Step4.若i等于n-1，将A[i][j]存入DP[i][j]，函数返回DP[i][j]；Step5.若i小于n-1，分别以(i-1,j)和(i-1,j-1)为参数递归调用函数f，返回值取较大者再加上A[i][j]，结果存入DP[i][j]，函数返回DP[i][j]。函数f定义结束；Step6.以参数（0,0）调用函数f，即f(0,0)，输出函数的返回值。动态规划（递归）设计思路：基于递归的动态规划算法的时间复杂度分析使用动态规划表格存储了已计算状态值，因此，处理的数字三角形是非重复的。对于一个n层的数字三角形，分解后形成的非重复三角形的顶点和原三角形各个数字是一一对应的。分解后需要处理的三角形总数即原三角形中数字总数。数字总数为n2/2，因此，基于递归的动态规划算法的时间复杂度为O(n2)。T(n)=n2/2

=O(n2)动态规划（递归）代码实现#include<stdio.h>#definemax(a,b)((a)>(b)?(a):(b))intn;//数字三角形层数intA[100][100];//存储数字三角形的数组intDP[100][100];//存储状态值的动态规划表格intf(inti,intj){//递归函数if(DP[i][j]!=-1)returnDP[i][j];//状态(i,j)的值已知

intres;//保存状态(i,j)的值的变量if(i==n-1)res=A[i][j];//初始状态值elseres=A[i][j]+max(f(i+1,j),f(i+1,j+1));//状态转移

DP[i][j]=res;//存储状态(i,j)的值returnres;//返回状态(i,j)的值}动态规划（递归）代码实现（续）intmain(){freopen("100.txt","r",stdin);//将标准输入重定向到文件scanf("%d",&n);//读取数字三角形层数for(inti=0;i<n;i++){for(intj=0;j<=i;j++){scanf("%d",&A[i][j]);//内循环读取三角形的第i行，j为列号

DP[i][j]=-1;//初始化动态规划表格}}printf("%d\n",f(0,0));//输出最终结果return0;}穷举算法

分治算法

动态规划（递归）

动态规划（递推）

目录动态规划（递推）任务描述：数字三角形问题自顶向下：基于递归的动态规划算法是一种自顶向下的方法，即从顶层的原问题开始向下进行分解，解决最小子问题后再依次向上合并。能否不使用递归实现DP?自底向上：另一种相反的思维方式是直接解决最小子问题，然后向上合并出更大子问题乃至原问题的解。最大“路径和”：对所有可能的路径求出“路径和”，最大者为最大“路径和”。图c的路径和为30，是所有“路径和”中最大者。动态规划（递推）相关知识：什么是递推递推：递推是一种自底向上的方法，具体而言，递推是一种从已知初始状态（最小子问题）开始，利用状态转移方程，从已知状态转移到未知状态的过程。

基于递推的欧几里得算法Input：正整数m和正整数nOutput：m和n的最大公约数Step1.m除以n，记余数为rStep2.如果r不是0将n的值赋给m，r的值赋给n，返回

Step1；否则，最大公约数是n，输出n，算法结束动态规划（递推）相关知识：基于递推的动态规划算法的基本步骤定义子问题：将原问题划分为若干个子问题，通常是原问题的一个子集，子问题可用一个状态来标识。建立递推关系：通过观察子问题之间的关系，将大问题转化为小问题，建立状态转移方程，以状态转移方程作为递推的基础。初始化边界条件：分析最小子问题，确定初始状态，以初始状态作为递推的边界条件。迭代计算：按照状态转移方程，从边界条件开始进行迭代计算，求解每个子问题，并使用DP表格记录中间结果。组合最优解：根据子问题的求解结果，通过组合或者选择操作，构造出整个问题的最优解。动态规划（递推）相关知识：基于递推的斐波那契数列问题的代码#include<stdio.h>intDP[10001];intmain(){intn,i;scanf("%d",&n);//读取n

DP[0]=DP[1]=1;//2个初始状态，值都为1

for(i=2;i<=n;i++)

DP[i]=DP[i-1]+DP[i-2];//递推printf("%d\n",DP[n]);//输出最终结果return0;}动态规划（递推）相关知识：动态规划的3个条件（1）问题具有最优子结构：若一个问题的最优解包含了其子问题的最优解，称其具有最优子结构性质。以斐波那契数列为例，“斐波那契数列的第i个元素”描述为f(i)，即问题的最优解为f(i)，两个子问题分别为“斐波那契数列的第i-1个元素”和“斐波那契数列的第i-2个元素”，分别描述为f(i-1)和f(i-2)，而f(i)=f(i-1)+f(i-2)表明问题的最优解可用其两个子问题的最优解相加获得，因此斐波那契数列问题具有最优子结构。动态规划（递推）相关知识：动态规划的3个条件（2）问题具有重叠子问题：重叠子问题指的是在问题分解过程中，重复出现的相同子问题，，下图中f(2)出现了3次，因此f(2)是一个重叠子问题，可以推断，求解f(6)时，需要计算f(2)的次数为3+2=5次，这也是一个斐波那契数列，随着问题规模的扩大，f(2)的计算次数也会呈指数级增长，实际上，除了f(2)，f(3)、(4)乃至f(n-2)都会存在重复的问题。动态规划（递推）相关知识：动态规划的3个条件（3）状态具有无后效性质：

无后效性质，指的是状态迁移时，新状态仅依赖于原先的一个或多个状态，而与到达原状态的路径无关。例如，对于斐波那契数列问题，任意状态i（i≥2）仅依赖于状态i-1和i-2，与以前如何转移到这两个状态无关。动态规划（递推）设计思路：数字三角形问题的递推求解方法初始状态：f(4,0)=A[4][0]=4->保存到DP[4][0]；f(4,1)=A[4][1]=5->保存到DP[4][1]递推：取第5层中相邻两个结果中较大者，加上其上顶点的值。结果保存在动态规划表格的相应位置，即：f(3,0)=max(f(4,0),f(4,1))+A[3][0]=max(4,5)+2=7->保存到DP[3][0]f(3,1)=max(f(4,1),f(4,2))+A[3][1]=max(5,2)+7=12->保存到DP[3][1]继续递推直到第一层......动态规划（递推）相关知识：数字三角形问题的递推算法Input:代表数字三角形的大小为n*n的二维数组A[n][n]Output:数字三角形的最大路径和Step1.定义动态规划表格DP[n][n]；Step2.；将初始状态值存入动态规划表格最后一行，即DP[n-1][j]=A[n-1][j]，0≤0<≤n-1；Step3.从倒数第2行（即i=n-2）开始递推，直到第一行（即i=0）为止；Step4.对于递推的每一行，状态(i,j)的求解方法为DP[i][j]=max(DP[i+1][j],DP[i+1][j+1])+A[i][j]，将状态值存入DP[i][j]；Step5.输出DP[0][0]的值，即问题的解。T(n)=n2/2

=O(n2)动态规划（递推）代码实现#include<stdio.h>#definemax(a,b)((a)>(b)?(a):(b))intn;//数字三角形层数intA[100][100];//存储数字三角形的数组intDP[100][100];//存储状态值的动态规划表格intmain(){freopen("100.txt","r",stdin);//将标准输入重定向到文件scanf("%d",&n);//读取数字三角形层数for(inti=0;i<n;i++){for(intj=0;j<=i;j++){scanf("%d",&A[i][j]);//内循环读取三角形的第i行，j为列号if(i==n-1)DP[i][j]=A[i][j];//初始状态}}动态规划（递推）代码实现（续）for(inti=n-2;i>=0;i--){//从倒数第2层开始递推for(intj=0;j<=i;j++){DP[i][j]=max(DP[i+1][j],DP[i+1][j+1])+A[i][j];//状态转移}}printf("%d\n",DP[0][0]);//输出最终结果return0;}给定不同长度（1英寸--24英寸）钢条的价格表如下图所示，对于长度为n的钢条，将之切割为短钢条出售，如何切割能获得最高价格，输出这个最高值。长度123456789101112131415161718192021222324价格15891017172024303334363842434649545860656670练习：钢条切割问题n为4时，共有8种不同的切割方案（如下图所示），其中方案c的价值最高。n为4的情形使用问题分解法来思考n=4的情形。考虑第一次切割的位置，只有4种情形（如图所示）。因此，第一次切割后，左边的长度是1、2、3、4中的一种，右边剩下的是一个规模更小的子问题，左边的不再切割，可直接从价格表获取价格。注意，左边长度为4时实际上不切割。最优解就是这4种情形的价值最大者。对于右边剩下的钢条，可继续分解成更小的子问题（再切下左边的一截，右边是更小的子问题）。原问题f(4)=max(P[1]+f(3),P[2]+f(2),P[3]+f(1),P[4])子问题f(3)=max(P[1]+f(2),P[2]+f(1),P[3])子问题f(2)=max(P[1]+f(1),P[2])子问题f(1)=max(P[1]+f(0));

子问题f(0)=0;这是边界状态其中P为价格表。n为4时的问题分解对于长度为n的钢条，考虑从左边切割下来长度为i(1≤i≤n)的一段，这一段不再分割，右边剩下的长度为n-i的继续分割(长度为n-i的子问题)，注意，i==n时实际上不切割；对所有可能的i，求所有分割方案的最大值，就是原问题的解。

右边剩下的长度为n-i是最优子问题，所以，钢条切割问题具有最优子结构。从n为4的分解可知，钢条切割问题具有重叠子问题（例如，f(4)和f(3)都要求解f(2)）。推广到n再来看n为4时的递归方式：f(4)=max(P[1]+f(3),P[2]+f(2),P[3]+f(1),P[4])递归函数的参数就是状态，本例中又代表了子问题规模的大小，这和数字三角形问题使用行号与列号作为状态是不同的。无后效性分析

从f(3)、f(2)、f(1)迁移到f(4)时，f(3)是如何从其他状态（哪个最大）迁移过来，不影响f(4)的值；因此，问题规模n具有无后效性，可以作为“状态”。状态转移方程

状态转移方程DP[0]=0;这是边界值DP[1]=max(P[1]+DP[0])=P[1]=1;DP[0]->DP[1];状态从0转移到1DP[2]=max(P[2]+DP[0],P[1]+DP[1])=max(5,1+1)=5;DP[0],DP[1]->DP[2]DP[3]=max(P[3]+DP[0],P[2]+DP[1],P[1]+DP[2])=max(8,5+1,1+5)=8;DP[0],DP[1],DP[2]->DP[3]DP[4]=max(P[4]+DP[0],P[3]+DP[1],P[2]+DP[2],P[1]+DP[3])=max(9,8+1,5+5,1+8)=10;DP[0],DP[1],DP[2],DP[3]->DP[4]递推过程中，求解DP[i]时，DP[i-1]..DP[0]都已解出，可顺利推进。能写出递归函数，就能通过其参数确定状态，然后确立状态转移方程，接着利用状态转移方程可以很容易地写出递推过程。最后，将递推过程用代码实现即可。n为4时递推过程有n种物品，它们有各自的体积和价值，现有背包容积为m，每种物品只能装入0次或1次（

所以称为01背包问题），如何让背包里装入的物品的价值总和最大，输出这个最大价值。例如，背包容量为9，有4种物品，体积和价值如下表所示(索引号都从1开始，0位置废弃，这样就不需要转换)：物品编号i1234体积w2345价值v3458练习：背包问题有如下组合方式：1编号1、2、3,W=2+3+4=9,V=3+4+5=122编号1、3,W=2+4=6,V=3+5=83编号1、4,W=2+5=7,V=3+8=114编号2、3,W=3+4=7,V=4+5=95编号2、4,W=3+5=8,V=4+8=126编号3、4,W=4+5=9,V=5+8=13显然，第6种方案是最优解。

物品编号i1234体积w2345价值v3458问题分析原问题：将4个物品装入容量为9的背包获得最大价值。考虑第4个物品，在原问题的最优解中，要么装入了第4个物品（假设背包容量≥w[4]），要么没有装入第4个物品。1

装入了第4个物品时，获得子问题a：将前3个物品装入容量为9-w[4]=9-5=4的背包获得最大价值。2

没有装入第4个物品时，获得子问题b：将前3个物品装入容量为9的背包获得最大价值。3

原问题的解=max(子问题a的解+v[4],子问题b的解)4子问题a和b按上述方式继续分解5

边界条件：物品数目为0、或者背包容积为0时，解为0。若背包容量<w[4],同样获得子问题a，且原问题的解=子问题b的解（无法装第4个物品）。问题分解

状态

状态转移方程物品总数为n，背包容量为m。定义DP[n][m]，