通俗的讲，算法是指解决问题的一种方法或一个过程；
严格的讲，算法是指由若干条指令组成的有穷序列，且满足以下性质：
程序是算法用某种程序设计语言的具体实现，程序可以不满足上述第四点性质（操作系统就是一个在无限循环中执行的程序，不是一个算法）；
在学习完毕算法设计与分析之后，应当按照如下流程来解决问题：
这个量应该集中反映算法的效率，并从运行这算法的实际计算机中抽象出来，换句话说，这个量应该是只依赖于要解的问题的规模、算法的输入和算法本身的函数；
如果分别用N、I和A表示算法要解的问题的规模、算法的输入和算法本身，而且用C表示复杂性，那么应该有C=F（N，l，A），其中F（N，I，A）是一个由N、I和A确定的三元函数；
注意一个问题，ei代表的是使用到元运算Oi的次数，但是我们不可能对规模为N的每种合法的输入I都统计ei（这也是不可能的事情，不管你排列组合学的多好...），所以上面那个式子必然还需要简化；
上述式子中，DN是规模为N的合法输入的集合，I*是DN中使T(N,I)达到Tmax(N)的合法输入，I~是DN中使得T(N,I)达到Tmin(N)的合法输入，P(I)是算法的应用中出现输入I的概率；
只限制情况还不够，现在需要计算机解决的问题的规模越来越大，因此引入复杂性渐近性态的概念；
假设T(N)是之前定义的关于算法A的复杂性函数，称T~(N)是T(N)当N趋于无穷时的渐近性态，直观上T~(N)就是T(N)中略去低阶项留下的主项，如T(N)=3n2+4NlogN+7时T~(N)=3N2
当n为具体数字的时候的Time值
这小节书上讲的的确是有点混乱了，到时候参考一下视频做修正
判定问题：判断是否有一种能够解决某一类问题的能行算法的研究课题；
书上讨论的大多数问题是以最优化问题的形式出现，对于每个最优化问题都存在与之对应的判定问题，一般情况下判定问题比相应的最优化问题多一个参数：
什么是NP类问题（Non-deterministicPolynomialProblem非确定性多项式问题）？在此之前我们首先需要了解非确定性算法的概念；
非确定性算法将问题求解分为猜测和验证两个阶段：
NPC包含了NP中最难的问题，解决了这个NPC问题，所有NP问题都能够被解决了；
分治思想与递归思想关系密切：
Q：递归和迭代的区别？
A：递归，就是在运行的过程中调用自己，构成递归需具备的条件：
总结：
在说递归之前不得不提及迭代，上面虽然稍微介绍了一下，我们这里再详细说一说；
//求1+2+3+…+n//递归funrecursive(n:Int):Int{returnif(n==0)0elsen+recursive(n-1)}//迭代funiteration(n:Int):Int{varresult=0for(iin1..n)result+=ireturnresult}直接拆解递归和迭代
使用递归:recursive(5)recursive(5)5+recursive(4)5+4+recursive(3)5+4+3+recursive(2)5+4+3+2+recursive(1)5+4+3+2+1+recursive(0)5+4+3+2+1+05+4+3+2+15+4+3+35+4+65+1015使用迭代:iteration(5)0+1=11+2=33+3=66+4=1010+5=15上面两个计算过程所需的步骤都是O(n)。但是两个计算过程的形状不一样。递归过程是一个先逐步展开而后收缩的形状，在展开阶段，这一计算过程构造一个推迟进行的操作（这里是+)所形成的的链条，在收缩阶段才会实际执行这些操作。这种类型的计算过程由一个推迟执行的运算链条刻画，称为一个递归计算过程，要执行这种计算过程，就需要维护将要执行的操作的轨迹。在计算1+2+3+…+n时，推迟执行的加法链条的长度就是为了保存其轨迹需要保存的信息量，这个长度随着n值而线性增长，这样的过程称为线性递归过程。
迭代过程的形成没有任何增长或收缩。对于任意一个n，在计算的每一步，我们需要保存的就只有i和return，这个过程就是一个迭代计算过程。一般来说，迭代计算过程就是那种其状态可以用固定数目的状态变量描述的结算过程。在计算1+2+…+n时，所需的计算步骤与n成正比，这种过程称为线性迭代过程。
使用递归的思想解决问题很容易，但是初学者可能对于递归思想解决问题存在困难，递归解题主要依据以下三个步骤：
递归解题固然很爽，但是因为“爆栈”的风险所以我们应该尽量少用，所以很多时候需要我们将递归进行非递归化，也称为迭代化（因为非递归也称为迭代）（当然使用尾递归的方式也可以避免“爆栈”，但是并非每一种递归都可以转换为尾递归的形式，并且也不是所有的编译器都支持尾递归的优化，我们这里主要还是介绍常用的迭代化方式）；
函数的递归调用本质是借助函数栈来实现的，函数递归的本质可以归结为如下几点：
（1）在函数递归调用之前将局部变量保存到栈中
（2）修改参数列表
（3）进行函数递归调用
（4）获得栈顶元素（恢复现场）
（5）弹出栈顶元素（释放内存空间）
递归迭代化的本质就是掌握函数栈的本质，注意当递归层次不是很深的时候没必要进行迭代化，因为迭代化之后的代码会变得比较难以理解；
顾名思义就是不断迭代展开递归方程，最后得到一个解析式；
当然这种方法也是一种将一个递归算法转换为一个非递归算法的方式
例题：
因为迭代展开的过程中经常涉及数列求和，所以下面总结一下常见数列的求和
当然迭代法也不会才那么点难度，有时候我们需要换元进行迭代：
将上述迭代展开的过程用一个树型的结构（递归树）来表示，递归树是迭代展开的可视化表示；
T(n)=2T(n/2)+n-1，其中T(n)首先作为树根，第一项是递归项，另一项是子问题的合并项，展开的时候将合并项放在上面，两个分支表示两个子问题：
下面的T(n/2)也是按照同样的方法进行展开：
最后我们可以得到如下完全展开后的迭代树：
先假设，之后使用数学归纳证明该猜想；
根据已经证明的一个主定理直接套用，得到特殊递归方程的解；
上述主定理也适用于子问题大小为n/b的上界，n/b的下界以及n/b+1的情况
当然上述主定理也可以用通俗一点的语言描述：
除了主定理1，还有主定理2
同理，用通俗的语言描述如下
求解递归方程不得不提及使用特征方程求解（当然还有生成函数、递推方法等，这里只介绍特征方程求解），这也是需要我们掌握的一种方法；
递归方程通常分为：
K阶常系数线性齐次递归方程
为了求解得到特征方程，需要
得到最终的特征方程如下
求得特征方程只是最基本的一个步骤，接下来的解题步骤如下：
需要考虑2种情况：
K阶常系数线性非齐次递归方程
更多关于K阶常系数线性非齐次递归方程的介绍就不再赘述，感兴趣可以自行百度；
稳定性是指排序后两个相等键值的顺序和排序之前它们的顺序相同，图中的In-place表示占用常数内存而不占用额外内存，Out-place表示占用额外内存，n表示数据规模，k表示“桶”的个数；
排序算法可以分为内部排序和外部排序：
下图展示了常见排序算法的一些简单描述，我们在之后还会详细对它们进行介绍（有些描述不太准确/甚至是错的，比如计数排序、桶排序，注意辨别）
算法步骤（当然也可以从左向右）：
最好情况：输入的数据都是正序（对于这种情况可以立flag，如果一趟序列遍历中元素没有发生交换则证明该序列有序）；
最坏情况：输入的数据都是反序；
选择排序顾名思义就是简单直观的选择序列中最小（大）的值将其放在序列最前（后）；
算法步骤：
如何在序列中寻找最小（大）元素呢？很简单，只需要遍历序列并每次都比较当前值和记录的最小（大）值，如果当前值更小（大）则更新最小（大）值；
插入排序实际上就是我们打扑克牌的常用策略，将最左端的牌固定不变（有序序列），右边的牌（未排序序列）比较大小并插入左边的牌堆；
希尔排序也称为递减增量排序算法，可以看作是插入排序的改进版本；
希尔排序的基本思想是：将整个待排序的记录序列分割为若干子序列，在这些子序列中分别进行插入排序，待子序列排序完成后，整个序列呈基本有序状态，此时对全体记录序列进行插入排序；
归并排序是一种建立在归并操作上的一种排序算法，归并排序主要有以下两种实现：
自下而上迭代实现：首先将原始序列看成N个只包含1个元素的有序子序列，然后每次迭代归并两个相邻的有序子序列，直到最后只剩下1个有序的序列。
voidMerge_sort_downtoup(){ intt=2;//最小分割单元 while(t<=n){ for(inti=1;i<=n;i+=t){ sort(a+i,a+min(i+t,n+1));//注意sort的使用 } /*这里可以进行一些操作*/ t*=2; } return;}自上而下递归实现：对一个数组（str）选中一个中间位置（mid=（start+end）/2），分别进行左递归（mergeSort（str，start，mid，length）），右递归（mergeSort（str，mid+1，end，length）），在回朔的时候分别对以中间为分割的数组进行排序（merge（str,start,end,mid）），此时是一个归并的过程，这是自上而下的方法。
voidmerge_sort_recursive(intarr[],intreg[],intstart,intend){if(start>=end)return;intlen=end-start,mid=(len>>1)+start;intstart1=start,end1=mid;intstart2=mid+1,end2=end;merge_sort_recursive(arr,reg,start1,end1);merge_sort_recursive(arr,reg,start2,end2);intk=start;while(start1<=end1&&start2<=end2)reg[k++]=arr[start1] 关于如何实现2，我们用下面的图进行解释 快速排序实质上就是利用L、R、pivot这些标记递归地重复一系列操作的算法； 堆排序利用了堆的数据结构，堆主要有如下两种： 堆是一种树形结构，是一种特殊的完全二叉树（完全二叉树不要求像满二叉树一样全部填满）； 桶排序是计数排序的升级版，它利用了函数的映射关系： 这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异： 基本思想 分治法在字面上的解释是“分而治之”，就是将一个规模为N的问题分解为K个规模较小的子问题(反复分解直到问题小到可直接求解为止)，使这些子问题相互独立可分别求解，再将k个子问题的解合并成原问题的解，这些子问题相互独立且与原问题性质相同(规模一般也相同)。只要求出子问题的解，合并就可得到原问题的解。 在分治法中，子问题的解法通常与原问题相同，这就导致递归过程，分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法； 适用情况 分治法能解决的问题一般具有以下4个特征：（1）当问题的规模缩小到一定的程度就可以容易地解决——这个特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加；（2）问题可以分解为若干个规模较小的问题，即该问题具有最优子结构性质——这个特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用； （3）利用该问题分解出的子问题的解可以合并为该问题的解（关键）——能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑用贪心法或动态规划法；（4）各个子问题是相互独立的，即子问题之间不包含公共的子问题——第四条特征涉及到分治法的效率，如果各子问题是不独立的则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法较好； 基本步骤 PS：将一个问题分成大小相等的k个子问题的处理方法是行之有效的； 算法设计模式： Divide-and-Conquer(P)1.if|P|≤n02.thenreturn(ADHOC(P))3.将P分解为较小的子问题P1,P2,…,Pk4.fori←1tok5.doyi←Divide-and-Conquer(Pi)//递归解决Pi6.T←MERGE(y1,y2,…,yk) //合并子问题7.return(T)其中: 复杂性分析 二分搜索算法用于高效地在有序数组A中查找一个目标值v，和线性搜索不同，二分搜索利用数据结构中的信息让搜索更高效； 原理 不断地搜索空间分成两半，将搜索空间限制在其中的一半；这个算法通过改变上下界限有效地限制搜索空间： 通过这个算法，如果目标值在这个数组中就可以保证： 在搜索的每一步中，只需要依次判定上界和下界中间的值 接下来，将中间值A[IndexMid]和目标值v进行比较： 这里举一个例子 第一个被判定的中点的值是11，比我们的目标值15小，因为我们知道这个数组是按照升序排列的，所以可以排除中点及其之前的所有部分，我们将下界索引移动到适当的地方(IndexLow=IndexMid+1) 在第二次比较之后，我们发现中点值是52，比目标值大。我们可以排除中点和它之后的所有部分。此时需要移动我们上界(IndexHigh=IndexMid-1) 请注意，通过这几次的操作，此时虽然下界已经是目标值了(v=15)，但是我们仍需要继续搜索，直到中间值指向目标值。这是因为二分搜索是对中间值进行判定，而不会判定上界和下界是否是目标值； 代码实现及复杂度分析 本质上快速排序是建立在冒泡排序上的递归分治法，算法步骤： 1.从数列中挑选一个元素称为基准pivot（一般都选择序列最左端的元素）；2.所有比pivot小的元素在pivot左边，所有比pivot大的元素在pivot右边（与pivot相同的数可以在任意一边）；3.递归地将小于pivot的子序列和大于pivot的子序列使用1、2步骤进行排序； 快慢指针完成单趟排序的思想非常简单，只需要遵循如下步骤：1.采用perv记录区间第一个元素的下标，采用cur记录区间第二个元素的下标；2.cur找小，每次遇到比key(坑值)小的值就停下来，++prev；3.交换prev和cur位置的值； 这样完成单趟的排序，因为我们需要实现整体的有序，这里选择了分治递归的思想：当左子区间有序，右子区间有序则该数组有序；综上，快速排序主要分为三个部分：三数取中、单趟排序、整体分治递归 代码实现 复杂度分析 平均和最好情况都是O(nlogn)，最坏情况是O(n2)； 选择问题：给定一个能够线性排序的集合（该集合中有n个元素，该集合是无序的）和一个整数k（1≤k≤n），找出这n个元素中第k小的元素； (1)随机划分线性选择 主要思想就是首先利用随机函数产生划分基准，将数组a[p:r]划分成两个子数组a[p:i]和a[i+1:r]，使a[p:i]中的每个元素都不大于a[i+1:r]中的每个元素； 接着令"j=i-p+1"来计算a[p:i]中元素个数j： 实现步骤： 总结：上述算法将每一组的大小定为5，并选取75作为是否作递归调用的分界点。这2点保证了T（n）的递归式中2个自变量之和n/5+3n/4=19n/20=en，0<<1，这是使T（n）=O（n）的关键之处。当然，除了5和75之外，还有其他选择。 主要考虑平面上的最接近点对问题，这类问题是计算几何学中研究的基本问题之一； 最接近点对问题：给定平面上的n个点，找出其中的一对点，使得在n个点组成的所有点对中，该点对的距离最小；严格来说最接近点对可能多于一对，简单起见规定只需要找出其中的一对作为问题的解； 考虑分治法的思想： 分解和求解步骤都不需要赘述，关键问题是合并步骤，如何由S1和S2两个子集中的最接近点对求得原集合S中的最接近点对，因为S1和S2的最接近点对未必就是S的最接近点对： (1)一维最接近点对问题 一维中原集合S中的n个点退化为x轴上的n个实数，最接近点对问题退化为n个实数中相差最小的两个实数； 由于每个长度为d的半闭区间至多包含S1中的一个点，并且m是S1，和S2的分割点，因此（m-d，m]中至多包含一个S中的点。同理，（m，m+d]中也至多包含一个S中的点。 由图2-8可以看出，如果（m-d，m]中有S中点，则此点就是S1中最大点。同理，如果（m，m+d]中有S中的点，则此点就是S2中最小点。 (2)二维最接近点对问题 问题描述 设有n个运动员要进行网球循环赛，设计一个满足下列条件的比赛日程表： 1）每个选手必须与其他n-1个选手各赛一次； 2）每个选手一天只能赛一次 3）当n是偶数时，循环赛只能进行n-1天 4）当n是奇数时，循环赛只能进行n天 依据数学方法，解决选手人数不等于2k时，在偶数和奇数情况下，依题目条件建立算法模型 原理分析 在进行算法设计之前我们先介绍当人数为2k的时候，这种最好的情况下应当如何分析。 首先我们设比赛人数为2（假如只有一个人则根本不需要比赛，没有分析的必要），比赛人数为2的比赛矩阵为[[1,2],[2,1]]，我们规定纵向为参赛人员编号，横向（除第一列）其他列为比赛天数。 接着分析比赛人数为4的情况，我们只需要将比赛人数为2的矩阵横向以及纵向扩充，扩充的规则是横向矩阵元素分别加原有矩阵的边长，作为基础矩阵2，接着分别将基础矩阵2和基础矩阵1逆序排列即可。按照上述规则，我们直接构造出人数为4的比赛矩阵[[1,2,3,4],[2,1,4,3],[3,4,1,2],[4,3,2,1]]。 根据上述规则，我们可以很容易的构造出比赛人数为2k的比赛矩阵，通过观察我们还能够发现这个矩阵是对称的矩阵。 接着我们尝试运用同样的分析方法来分析非2k人数的情况。 从上面的分析可以看出，使用这种简单的递归方法是不能解决这种非特殊情况的，所以我们需要考虑使用其他方式； 这道题并不是仅仅只需要无限划分矩阵就可以做出来这么简单，我们需要自底向上构造，当比赛人数为奇数的时候需要额外增加一个虚拟选手使得其他选手与之比赛，在最后需要将该虚拟选手删除并将其他选手与之比赛的安排置零 算法设计 首先是分治法的分治过程 注意这里我们需要做一个简单的判别 本程序最关键的点就在于子问题的合并过程，这同时也是元素矩阵的构造过程 分治法的基本思想就是先算出n/2的情况，接着将n/2的子问题进行合并构造出n的情况。 我们将构造过程分为了横向构造和纵向构造，横向构造通过已知的前m个选手的比赛安排来确定后n-m个选手的比赛安排，纵向构造通过已知的前before_days的比赛安排来确定后days-before_days天的比赛安排。 在横向构造的过程中需要注意的是，当我们总人数是奇数的时候，我们会额外增加一行（我们默认横向为比赛天数，纵向为参赛选手编号），之所以增加一行是为了按照和偶数一样的边界进行构造，而实际上这个参赛选手是不存在的，所以在最后我们需要将与该选手进行比赛的其他选手的相应位置设置为空或0，表示该选手在这天休息不进行比赛。 在纵向构造的过程中需要注意一点就是需要避免矩阵元素重复，解决方法是使用一个标记来标志子问题是否为奇数，如果是则构造的纵向增量需要额外+1，这样就能够保证A【1】【j】不重复进而保证之后的构造增量不重复。 首先抛出一个问题，很多人认为有平时的乘法的为什么还需要大整数呢？这不是多此一举？这是因为计算机硬件或者软件的限制，无法存储那些非常大的数字（尤其是在某些特殊领域），所以就需要使用特殊手段对其存储并且能够设计有效的运算法则对其进行运算； 简单大整数乘法 首先我们来介绍一下什么是大整数乘法；大整数又被称为高精度整数，之所以称之为高精度整数是因为这样的整数用基本数据类型无法存储其精度，因此一般使用数组来存储大整数，数组中的每一位都代表了大整数的每一位：整数的高位存储在数组的高位，整数的低位存储在数组的低位，之所以这样存储是因为运算的时候都是从整数的低位到高位进行枚举，使用顺序存储是符合这种思维的；输入大整数时，一般都是先用字符串读入，然后再把字符串另存为至大整数结构体bign（该结构体包含大整数数组d[]和大整数长度len）。由于使用char数组进行读入时，整数的高位会变成数组的低位，而整数的低位会变成数组的高位，因此为了让整数在bign中是顺位存储，需要让字符串倒着赋给d[]数组（这点很重要，之后的代码我们会使用到char数组来接收大整数）； 因为编程语言提供的基本数值数据类型表示的数值范围有限，不能满足较大规模的高精度数值计算，因此出现了大整数运算来实现高精度的数值计算，下面我们将介绍大数运算中的乘法运算。 在计算机中存储的整数都是二进制形式，大整数乘法首先需要将nbit二进制整数X和Y都分为2段，每段长度都是n/2bit（为了方便讨论认为n是2的幂次） 那么可以将X和Y表示为 那么大整数X和Y的乘积就是 为了改进算法的计算复杂度，需要减少乘法次数，对上式进行优化得到 FFT改进大整数乘法 我们知道FFT是用来加速计算多项式乘法A(x)*B(x)=C(x) 那么FFT和大整数乘法有什么关系呢？为什么可以使用FFT来实现大整数乘法的优化？ 下面我们介绍一下FFT到底是什么，因为FFT整个过程比较复杂，我们直接用手写的方式给出介绍 FFT的代码实现 动态规划是运筹学的一个分支，是求解决策过程最优化的数学方法；在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，把多阶段过程转换为一系列单阶段问题，利用各个阶段之间的关系逐个求解，这就是动态规划的算法； 阶段 把所给求解问题的过程恰当地分成若干个相互联系的阶段，以便于求解，过程不同，阶段数就可能不同； 将描述阶段的变量称为阶段变量： 在前面的图中，第一个阶段就是点A，而第二个阶段就是点A到点Bi，第三个阶段是点Bi到点Ci，而第四个阶段是点Ci到点Di 状态 状态表示每个阶段开始面临的自然状况或客观条件，它不以人的主观意志为转移，也称为不可控因素。 在上面的例子中状态就是某阶段的出发位置，它既是该阶段某路的起点，同时又是前一阶段某支路的终点。图中，第一个阶段有一个状态A，而第二个阶段有三个状态B1、B2和B3，第三个阶段有三个状态C1，C2和C3，而第四个阶段有两个状态D1和D2； 无后效性 要求状态具有下面的性质：如果某阶段的状态一旦确定，则在这一阶段以后过程的发展变化仅与此阶段的状态有关，不受这阶段以前各段状态的影响，所有各阶段都确定时，整个过程也就确定了； 简单来说，过程的每一次实现可以用一个状态序列表示；在前面的例子中每阶段的状态是该线路的始点，确定了这些点的序列，整个线路也就完全确定；从某一阶段以后的线路开始，当这段的始点给定时，不受以前线路（所通过的点）的影响； 即未来与过去无关，当前的状态是此前历史（以往决策）的一个完整总结，过程的历史只能通过当前的状态去影响它的未来的发展，这个性质称为无后效性（简单点说：过去只能通过影响现在，进而影响未来） 决策 一个阶段的状态给定以后，从该状态演变到下一阶段某个状态的一种选择（行动）称为决策；在最优控制中，也称为控制；每一个阶段都有若干个决策可供选择；在许多问题中，决策可以自然而然地表示为一个数或一组数；不同的决策对应着不同的数值；描述决策的变量称决策变量，因状态满足无后效性，故在每个阶段选择决策时只需考虑当前的状态而无须考虑过程的历史； 决策变量的范围称为允许决策集合； 多阶段决策问题 如果一类活动过程可以分为若干个互相联系的阶段，在每一个阶段都需作出决策(采取措施)，一个阶段的决策确定以后，常常影响到下一个阶段的决策，从而就完全确定了一个过程的活动路线，则称它为多阶段决策问题； 各个阶段的决策构成一个决策序列，称为一个策略，每一个阶段都有若干个决策可供选择，因而就有许多策略供我们选取，对应于一个策略可以确定活动的效果，这个效果可以用数量来确定。策略不同，效果也不同，多阶段决策问题，就是要在可以选择的那些策略中间，选取一个最优策略，使在预定的标准下达到最好的效果； 策略 由每个阶段的决策组成的序列称为策略。对于每一个实际的多阶段决策过程，可供选取的策略有一定的范围限制，这个范围称为允许策略集合。允许策略集合中达到最优效果的策略称为最优策略； 状态转移方程 最优化原理 一个问题满足最优化原理也称其拥有最优子结构性质； 如何证明要解决的问题具备最优子结构？主要步骤如下： 好了，动态规划的术语介绍完毕，是不是懵了？我也很懵，咱们实际上只需要简单过一遍这个概念即可，真正重要的还是刷题理解，概念性的知识不用硬磕； 动态规划算法主要用于求解最优性问题，此类问题通常具有许多可行解，我们需要找到具有最优值的解； 动态规划的定义：动态规划(DP：DynamicProgramming)是一种重要的程序设计手段，其基本思想是在对一个多阶段决策的问题，按照某一顺序，根据每一步所选决策的不同会引起状态的转移，最后会在变化的状态中获取到一个决策序列； 动态规划和分治法的异同： 动态规划的实质是分治思想和解决冗余的结合： 动态规划的基本思路：用一个表来记录所有已解的子问题的答案，不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中；具体的动态规划算法多种多样，但它们具有相同的填表格式； 这里需要补充的一个概念是备忘录算法； 备忘录算法的定义：备忘录方法是动态规划算法的变形，它通过分治思想对原问题进行分解，以存储子问题的解的方式解决冗余计算，并采用自顶向下的递归方式获取问题的最终解； 备忘录算法和动态规划算法的异同： 解题主要按照如下步骤进行即可： （1）分析最优解的性质，并刻画其结构特征 //确定满足最优化原理、划分阶段、确定状态（2）递归地定义最优解 //确定状态转移方程(递推方程)（3）以自底向上或自顶向下(备忘录)的方式计算出最优值(这一步就是为了构造最优解做准备)（4）根据计算最优值时得到的信息，从子问题的最优解逐步构造出整个问题的最优解(如果只需要求出最优值(如矿工获取的钻石数量最大值)则该步骤可以省略)下面我们详细讲一下解题步骤中的细节，当然考试的时候只需要按照上述四个步骤即可，这里的细节是为了初学保证理解透彻； 首先是将原问题分解为子问题(划分阶段)： 接着确定状态和状态空间： 然后是确定状态转移方程，即如何从本阶段状态到达下一阶段未求解状态 最后就可以开始计算了，以自底向上或自顶向下的记忆化方式（备忘录法）计算出最优值，根据计算最优值时得到的信息，构造问题的最优解 动态规划的主要难点在于理论上的设计，使用动态规划求解问题，最重要的就是确定动态规划三要素：（1）问题的阶段(子问题划分)；（2）每个阶段的状态；（3）从前一个阶段转化到后一个阶段之间的递推关系(从这个程度上来说动态规划往往可以使用递归程序来实现)； Q：动态规划和递归之间的关系？ 动态规划：一种解决问题的算法思想，与之同属于算法思想的有：枚举（暴力）、分治、贪心等； 递归：一种具体的代码结构，即在本函数中调用了本身。与之同属于代码结构的有：递推（迭代）； 动态规划和递归的关系可以理解为：动态规划是解决问题的一种算法思想/题型，具体的实现/解题方法可以用递归； 问题描述：给定n个矩阵，其中Ai和Ai+1是可乘的(也就是前者的列等于后者的行，乘积矩阵的行数等于前者行数，列数等于后者列数)，请求解这n个矩阵的连乘积； 由于矩阵乘法满足结合律，因此计算矩阵的连乘积可以有不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，即该连乘积已完全加括号，则可依此次序反复调用两个矩阵相乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘积可递归地定义为： 举例来说矩阵连乘积可以有如下5种完全加括号的方式 每种完全加括号方式对应一种矩阵连乘积的计算次序，而矩阵连乘积的计算次序与其计算量有密切关系（这个其实在学习线性代数的时候已经可能有体会了，不同的计算次序会导致不同的计算量）； 我们这里简单举个例子，首先我们直接给出计算两个矩阵的乘积的标准算法需要三重循环，假设A是pxq矩阵，B是qxr矩阵，则总共需要pxqxr次数的乘法； 设3个矩阵的维数分别为10×100、100×5和5×50。若按第一种加括号方式（（A１A2）A3）计算，3个矩阵连乘积需要的数乘次数为10×100×5+10×5×50=7500。若按第二种加括号方式（A１（A2A3））计算，3个矩阵连乘积需要100×5×50+10×100×50=75000次数乘。第二种加括号方式的计算量是第一种加括号方式计算量的10倍。由此可见，在计算矩阵连乘积时，加括号方式即计算次序对计算量有很大影响； 因此实际上矩阵连乘问题就转换成了确定矩阵连乘积的计算次序使得数乘次数最少的问题； (1)穷举搜索法 即穷举出所有可能的计算次序，计算每种计算次序需要的数乘次数，从中找出数乘次数最少的计算次序； 对于n个矩阵的连乘积，假设拥有P(n)种不同的计算次序，考虑以第k个矩阵为分割线，将原连乘序列分为两个连乘子序列，接着分别对这两个连乘子序列加括号，最后对综合结果加括号得到原矩阵序列的完全加括号方式，可以得到关于P(n)的递归式子如下： (2)动态规划算法 动态规划算法按照以下步骤进行即可 a)分析最优解的结构 设计求解具体问题的动态规划算法的第一步是刻画该问题的最优解的结构特征，这里为了简化表示将矩阵连乘积记为A[i:j]； 现在需要计算A[1:n]的最优计算次序(也就是连乘序列加括号的问题)，还是将其划分为两个子序列求解，因此总计算量等于A[1:k]加上A[1+k:n]加上A[1:k]乘以A[k+1:n]的计算量； 我们可以发现，子序列连乘A[1:k]和A[1+k:n]在A[1:n]最优的情况下的计算次序也是最优的，因此，矩阵连乘积计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法求解的显著特征； b)建立递归关系 设计动态规划算法的第二步是递归地定义最优值； 规定计算A[i:j]所需要的最少数乘次数为m[i,j]，因此原问题A[1:n]的所需的最少连乘次数为m[1,m]； c)计算最优值 LCSLength以序列X和Y作为输入，输出两个数组c和b，其中c存储Xi和Yj的最长公共子序列的长度，最终问题的最优值（X和Y的最长公共子序列的长度），b存储c对应的元素的值由哪个子问题的解得到，用于构造最优解使用； d)构造最长公共子序列 前面构造得到的数组b可用于快速构造序列X和Y的最长公共子序列： 下面的算法LCS实现根据b的内容打印出Xi和Yj的最长公共子序列，通过算法调用LCS（m,n,x,b）便可打印出序列X和Y的最长公共子序列 问题描述： 我们这里总结一下几个经典解决方法的复杂度即可 暴力枚举 分治法 动态规划 0-1背包问题：给定n种物品和一个背包，物品i的重量是wi，其价值为vi，背包的容量是c，应当如何选择装入背包中的物品才能使得装入背包中物品的总价值最大； 在选择装入背包的物品时，对每种物品i只有两种选择，即装入背包或不装入背包，需要注意的是不能将物品i装入背包多次（可以看作是只有一个物品i，装入了就没了），也不能只装入部分的物品i；因此该问题称为0-1背包问题； 关于几类背包问题的区别： a)最优子结构性质 b)递归关系 需要注意的是，在这一步很重要的一点其实是确定dp数组的定义，本题的dp数组就是m(i,j)，意义是下标为0-i之间的物品任取，放入容量为j的背包中的最大价值，在之后的推导递归公式、初始化以及确定遍历顺序的时候都是围绕着dp数组的含义来进行； 接着我们需要确定dp数组可以从哪几个方向推导出来（确定递推公式），对于m(i,j)来说，有两种选择，这两种选择中取最大值 c)算法描述 矿工问题也称为金字塔问题； 经典版钻石矿工 我们之所以先介绍经典的钻石矿工问题是为了更好的理解蒙图版本的钻石矿工问题。 经典钻石矿工的问题描述如下：有一座金字塔，金字塔的每块石头上都镶有对应的钻石，钻石可以被取下来，不同的钻石有着不同的价值，你的任务是从金字塔的顶端向金字塔的底端收集钻石，并且尽可能收集价值高的钻石，但是只能从一块砖斜向左下或斜向右下走到另一块砖上。请找到一个收集最高价值钻石的路线，并给出能够获得的最大钻石总价值？ 本算法的主要设计思路是动态规划，首先根据金字塔每块砖的位置，使用二维数组将其进行存储，如上图所示，可以看出元素都存储在下三角内。 可以将该问题用一个二元组A(x,y)来表示，A(x,y)表示从第x层第y个位置到达底层的最大价值，这样A(x,y)的最优路径Path(x,y)一定包含子问题A(x+1,y)和A(x+1,y+1)的最优路径，原问题的最大价值可以表示为A(1,1)。 该问题因为具有最优子结构的性质，所以可以使用动态规划算法，对每个子问题只解一次，接着将解保存下来，递归关系如下（其中α(x,y)表示第x层第y个位置的值） 从倒数第二层开始，每个位置只需要将自己下方可达的两个位置进行比较即可得到该位置的最大价值； 蒙图版钻石矿工 蒙图版问题是基于传统钻石矿工问题之上，在实际应用中，矿工事先往往无法提前知道金字塔的钻石分布。通常，他们只能估计面前两个方块内的钻石数，或者租用探测器来获得面前x步（x 这些情况下的信息量会对矿工的收益造成与传统钻石矿工问题不同的结果； (1)上帝视角 我们首先讨论矿工探测范围为无限大的情况，使用ans数组存储确定状态，即ans[x][y]表示矿工从出发点到位置(x,y)的最优值，同时使用route数组存储节点向左还是向右，便于之后生成最优路径； 我们简单解释一下上述代码的逻辑，在此之前我们应该知道传统的钻石金字塔有两种解法，分别是正序遍历（即从上往下）和逆序遍历（即从下往上），这里我们选择了逆序遍历，也就是从金字塔的最下面一层开始逐层向上遍历，这样最后ans数组的第一个元素存储的值就是整个金字塔最优路径的值； 在逆序遍历之前，需要先初始化ans数组最后一层的元素，直接使用pyramid数组的对应元素初始化即可，ans数组的其他位置我们初始化为0，等待之后的计算； 接着我们从倒数第二层开始计算，计算方法实际就是比较当前节点加上左孩子节点或当前节点加上右孩子节点的较大值，需要注意的是最好从第二层的最后一个节点往第一个节点计算，否则很容易出现ans数组的节点的值不是正确的值（这点是在实际写代码的时候发现的）；之所以会出现这种情况是因为我们使用的是如下形式的二维数组存储金字塔，如果从前往后计算需要严格规定循环条件，否则容易导致某些节点不参与计算； 我们计算route数组的方式很简单，当该节点选择了自己的左孩子节点则标记route数组对应元素为1，当该节点选择了自己的右孩子节点则标记route数组对应元素为2； 在之后输出结果的时候，我们使用一个for循环，利用if判断，当节点对应的route数组元素为1则向下移动（金字塔的左孩子实际就是二维数组的向下，之后不再强调），节点对应的route数组元素为2则向右移动，依次coutpyramid数组的元素即可得到最优值对应的俄最优路径； (2)探测范围为1 对应于上帝视角的极端情况就是矿工只能看到自己下一步的两个矿的钻石数量，这就意味着他无法进行全局规划，这里我们选择了使用贪婪算法，即矿工每次都选择自己所看到的钻石数量最大的矿（这当然会导致问题，我们之后会展示），贪婪算法不一定能找到全局最优值，但是可以找到矿工所见的最优值，也就是局部最优值 贪婪算法实现如下，算法思想很简单，矿工只会选择自己左边和右边的矿之一，选择依据是值较大者，这里借助了递归的思想，递归终止条件为矿工到达最底层，代码上体现为二维数组的横坐标加纵坐标值等于深度加1； 我们仍然借助了一个route数组，用于保存节点选择的移动方向（向左或向右），在最后输出结果的时候给出最优值对应的最优路径（当然这里只能是局部最优路径） (3)探测范围为m 之所以要先介绍上帝视角和探测范围为1的情况实际就是为了这种情况做铺垫； 假设现在矿工租用了一个探测范围为m的探测器，可以知道自身节点往下m范围的矿产资源，现在该如何设计算法？ 我们将这个问题分解，首先矿工处于(1,1)的起点位置，他知道接下来m的矿产，这里为了方便说明因此直接举实例，我们的金字塔如下 假设m=2，则矿工眼中的矿产分布如下 现在矿工有四个选择，分别是330+519、330+142、301+142、301+872，根据局部最优原则，矿工会选择移动到(2,1)，此时矿工的地图被更新 同样的，矿工面临四个选择，分别是142+155、142+358、872+124、872+358，毫无疑问，矿工会选择移动到(3,1)，此时矿工的地图更新 矿工面临四个选择：358+226、358+424、124+424、124+189，因此矿工移动到(3,2) 接着矿工更新自己的地图（注意我们的pyramid是1001*1001大小的，在未赋值的地方全部初始化为0也是为了方便计算） 毫无疑问，矿工会选择424，因此探测范围为2的最优值为326+301+872+358+424=2281（稍后我们会使用算法验证） 可以很明显的体会到，假设矿工的探测范围为m，矿工处于(x,y)的位置，则矿工可以看到的金字塔信息为(x,y)(x+1,y)…(x+m,y)…(x,y+1)…(x,y+m)，简单来说矿工实际上是知道以自己为中心的范围为m的上帝视角的金字塔的，那么问题就变得很简单，矿工只需要分别对左下和右下进行m-1大小的上帝视角算法得到最优值，接着比较左下和右下的值得到较大者，向下移动，接着重复上述操作即可；实现代码如下 Dynamic函数是这部分的核心，需要注意的是严格控制好边界条件，这里的倒三角数组因为x和y值不是严格对应的，所以不能直接套用前面实现上帝视角的代码，for循环的边界条件最好纸上作图手动确定，当然这里我们还是选择的逆序遍历，最终直接returnans数组的第一个元素即ans【x】【y】即可； Scope_m_comparation函数是一个递归函数，主要实现比较左孩子和右孩子的m-1最优值，将较大者加入result结果并保存路径节点至route数组中；需要注意的是这里传入dynamic函数的steps需要减去1，因为steps只是当前处于(x,y)节点的探测范围，但是对于(x+1,y)或者(x,y+1)来说其探测范围就变成了steps-1； 代码总结 在本次实验中主要遇到了如下问题：探测范围为m的代码逻辑出错导致最终结果不正确、递归算法的单层递归逻辑不好确定以及正序遍历和逆序遍历的选择、二维数组存储金字塔的选择； 首先是如何使用二维数组存储金字塔，常见的方法有使用左上三角存储和左下三角存储，我们这里选择了使用左上三角存储的原因是为了更方便的观察和处理金字塔，同时将金字塔从数组的(1,1)位置开始存储，其他位置赋值为0，之所以这样做是为了便于之后的计算，当探测范围m加上当前矿工位置(x,y)超出了金字塔的范围的时候，因为超出部分被赋值为0所以不会对求和结果做出影响，这意味着我们不需要额外处理这种情况； 那么应该如何选择遍历顺序呢？其实这里选择正序和逆序都是可以的，但是对我个人来说逆序遍历更好理解，同时ans数组的首元素就是最终的最优值，直接cout即可，非常方便； 选择了逆序遍历就一定要注意遍历的逻辑，首先初始化ans对应pyramid的最后一层，接着从倒数第二层的最后一个节点使用逻辑max(left,right)+pyramid(x,y)即可得到ans数组每个节点的值，因为是从下向上、从右向左，所以外层循环和内层循环都是递减操作，边界条件是行数不低于x、列数不低于y，针对每层的节点的遍历，保持x值不变，y值递减即可，需要注意起始节点(也就是每层得最后一个节点)的位置是依赖于i和x以及steps值的，这里只需要简单的求解一个二元方程即可得到j值和i的关系； (1)暴力枚举 上述算法重复做了很多工作，每次计算A[i]~A[j]都要从A[i]一直累加到A[j]，实际上我们可以先保存A[i]至A[j-1]的和到一个变量中，则A[i]至A[j]的和等于该变量+A[j]，只需要两层循环 分治策略基本思想是把问题规模分解为多个小规模问题，递归地解这些子问题，然后将各子问题的解合并得到原问题的解，一般采用二分法逐步分解（很可能还需要借助递归）； 本题目的分治思想为，序列A[0:n-1]分为长度相等的两段子序列A[0:n/2-1]和A[n/2:n-1]，分别求出两段子序列最大子段和，则总序列的最大子段和可能情况如下： 使用二分法做分治的终止条件为，直到每个子序列只有一个或两个数： 动态规划与分治法的相同点： 动态规划与分治法的区别： 这道题的动态规划思想如下： 已知前n个数的最大子段和，那么前n+1个数的最大子段和有两种情况，一是包含前面的结果，二是不包含； 动态规划一项很重要的内容就是保存各个阶段的状态，我们这里只需要使用MaxSum来保存前一个状态即可 所谓贪心算法，就是总是做出在当前看来是最好的选择(未从整体考虑)的一种方法； 贪心策略总是做出在当前看来是最优的选择，也就是说贪心策略并不是从整体上加以考虑，它所做出的选择只是在某种意义上的局部最优解，而许多问题自身的特性决定了该问题运用贪心策略可以得到最优解或较优解(注：贪心算法不是对所有问题都能得到整体最优解，但其解必然是最优解的很好近似解，同时对范围相当广泛的许多问题它的确能产生整体最优解）； 贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。选择的贪心策略必须具备无后效性； 需要解决的问题具备如下性质才能使用贪心算法解决： 实际上，贪心算法适用的情况很少，一般，对一个问题分析是否适用于贪心算法，可以先选择该问题下的几个实际数据进行分析，就可做出判断； 贪心算法的局限性： 贪心算法是动态规划方法的一个特例，可以证明每一个子树的根的值不取决于下面叶子的值，而只取决于当前问题的状况。换句话说，不需要知道一个节点所有子树的情况，就可以求出这个节点的值。由于贪心算法的这个特性，它对解空间树的遍历不需要自底向上，而只需要自根开始(自顶向下)，选择最优的路，一直走到底就可以； 动态规划和贪心算法都是选择性算法，在进行决策选择时： 结论：贪心算法是动态规划的特例，所有的贪心算法都可以使用DP求解； 贪心算法采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪心法不需要回溯； 主要的解题步骤如下： 贪心算法的一般算法模块如下（实际上贪心算法并没有固定的解题模板） 贪心算法GreedySelector并不总能求得问题的整体最优解。但对于活动安排问题，贪心算法总能求得的整体最优解，即它最终确定的相容活动集合A的规模最大。这个结论可以用数学归纳法证明。 算法首先选择活动1，并将j初始化为1，接着检查活动i是否与A集合中的所有活动相容： 背包问题与0-1背包问题注意区分，尽管这两类问题都有最优子结构的性质，0-1背包不能用贪心求解，但是背包问题可以使用贪心求解 对于0-1背包问题，贪心选择之所以不能得到最优解是因为，在这种情况下，它无法保证最终能将背包装满，部分闲置的背包空间使每千克背包空间的价值降低了（因为物品1每千克价值最大所以首选物品1，但是看图可以发现首选物品1的两种方案都不是最优的，应当选择物品2和物品3）； 用贪心算法解背包问题的基本步骤是：首先计算每种物品单位重量的价值vi/wi；然后依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过c，则选择单位重量价值次高的物品并尽可能多地装入背包。以此策略，一直进行下去，直到背包装满为止。具体算法可描述如下： 最优编码/最优前缀码问题：给出n个字符的频率ci，给每个字符赋予一个01编码串，使得任意字符的编码不是另一个编码的前缀，且编码后的总长度尽量小（总长度：每个字符的“频率*编码长度”的总和） 哈夫曼提出了构造最优前缀码的贪心算法，由此产生的编码方案称为哈夫曼算法，哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树T； 该最有前缀码的二叉树T具有以下性质，对这些性质的证明也就是对哈夫曼算法正确性的证明： 因为哈夫曼编码较难，所以这里我们就不再详细介绍如何证明哈夫曼算法的正确性（即证明最优前缀码问题具有贪心选择性质和最优子结构性质），感兴趣可以参考《计算机算法设计与分析第五版》P104 关于迪杰斯特拉算法的正确性和复杂性证明，感兴趣可以参考《计算机算法设计与分析第五版》P107 关于这两个算法的设计实现参考《计算机算法设计与分析第五版》P108，而这两个算法的正确性教材并没有证明，所以我们也不拓展； 最优装载问题的难度不是很大，我们这里主要讨论该问题的贪心选择性质和最优子结构性质应该如何证明； 贪心选择性质（数学归纳法） 最优子结构性质（反证法） 最优装载问题可用贪心算法求解，采用重量最轻者先装的贪心选择策略，可产生最优装载问题的最优解，具体算法描述如下： 回溯法也称为试探算法，回溯法的求解目标一般是找出解空间树中满足约束条件的所有解； 回溯和递归相辅相成，只要有递归就会有回溯（一般意义上我们所说的回溯函数实际上就是递归函数），回溯通常都是隐藏在递归函数的下面（递归函数下面的部分就是回溯的逻辑，没有人会去用迭代实现回溯(回溯是复杂递归，拆分为迭代的复杂程度极其大)）； 回溯法的本质是穷举所有的可能选出我们想要的答案，所以回溯法尽管很难理解但实际上效率并不是很高； 但是有些问题还真的就只能使用暴力穷举能做（for循环嵌套根本求解不出来），我们能够对回溯法做的优化最多就是加一些剪枝的处理，回溯法一般用于解决如下类型的问题： 因为回溯法解决的问题抽象出来都是在集合中递归的查找子集，此时集合的大小构成了树的宽度，递归的深度构成了树的深度； 在此之前介绍一些术语： 约束函数和限界函数的目的是相同的，都为了剪去不必要搜索的子树，减少问题求解所需实际生成的状态结点数，它们统称为剪枝函数； 回溯法/分支限界法=穷举+剪枝 回溯法是一个既带有系统性又带有跳跃性的搜索算法 这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，本质上回溯法就是对隐式图的深度优先搜索算法； 回溯是穷举方法的一个改进，它在所有可行的选择中，系统地搜索问题的解。它假定解可以由向量形式(x1,x2,...,xn)来表示，其中xi的值表示在第i次选择所作的决策值，并以深度优先的方式遍历向量空间,逐步确定xi的值，直到解被找到； 若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束，来确保解的正确性，若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束； 回溯法的使用情况： 有许多问题，当需要找出它的解集或者要求回答什么解是满足某些约束条件的最佳解时，往往要使用回溯法，(找出解空间树中满足约束条件的所有解)；回溯法的基本做法是搜索，或是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法，这种方法适用于解一些组合数较大的问题； 当然上述解题步骤只是泛泛而言的理论解题步骤，我们再给出具体的如何写代码的解题步骤 回溯算法的模板框架如下（之后的回溯算法几乎都是在这个框架上建立的） voidbacktracking(参数){if(终止条件){存放结果;return;}for(选择：本层集合中元素（树中节点孩子的数量就是集合的大小）){处理节点;backtracking(路径，选择列表);//递归回溯，撤销处理结果}}2.范例2.1轮船装载问题该算法可以看作是贪心算法的轮船装载问题的变形（实际上应当是我们下面介绍的普通装载的拓展），问题描述如下 算法思路 分别使用如下数据结构表示问题和解 我们定义一个dfs函数来求解该问题（即求解算法） 求解步骤 简单装载问题的求解与幂集问题是同类问题，它们对应的解空间树都是一棵子集树，但不同的是简单装载问题是一个最优解问题——每找到一个可行解，就需要与最优解进行比较以得到最优解 幂集求解时每个节点都可以拓展出两个节点，但是简单装载问题不需要拓展所有的节点，即在求解过程中可以剪枝，通过剪枝可以提高求解速度； 对应的剪枝方式有两种（原因是什么写出对应的情况就知道了，当然也可以按照下面的流程图进行理解，流程图中需要注意的是我们采用的是第一种右剪枝方式） 可能上述描述比较抽象，这里直接给出实际的过程（参考视频更好理解，注意为什么数组第一个元素为0占位不使用这涉及数据结构） 最后要说的一点，为什么上述算法体现了回溯？因为我们如果不回溯的话只会按照一条路径向下搜索，但是这里的算法搜索完毕后会回到上一个节点考虑另一条路径的拓展，在代码中回溯体现的都不一样，可以使用path.pop_back()也可以使用op[i]=0等不同的方式，具体取决于使用的数据结构； 简单装载问题是一个最优解问题，复杂装载问题是一个可行解问题； 复杂装载问题可以借助简单装载方案解决，可以这样考虑如下问题 分别使用如下数据结构描述问题以及表示解 我们使用dfs表示求解算法 接着统计第一艘装完后剩余的集装箱重量sum；若sum<=c2，表示第二艘轮船可以装完，返回true；否则表示第二艘轮船不能装完，返回false； 关于代码我们就不展开讲解了，感兴趣可以去视频里好好看一下； 实验代码参考： 旅行售货员问题travellingsalesmanproblem，问题描述如下 可以很清楚的看到这是一个汉密尔顿回路问题，即从图中一点出发，经过所有点一次之后又重新回到起点，称该回路为汉密尔顿回路；可以知道这是一个NP问题，所以只能采用递归穷举+剪枝的方式解决； 解题步骤 算法实现 对应的算法如下 实例 对应算法的实现作图得到如下解空间树 算法效率分析 简单来说规则就是： 之前处理的问题都只是简单的一维集合，本题是需要处理一个二维的数组，即如何使用回溯法搜索二维棋盘； 最暴力的方式当然就是嵌套for循环，即假如给的是一个4*4的棋盘则嵌套四个for循环分别遍历每一行，但是随着棋盘的增大暴力显然是不能解决的，所以本题需要使用回溯法解决； 问题分析 这里使用一个3*3的棋盘举例； 可以看到3*3的N皇后是一个无解问题； 根据回溯法的三大步骤，首先确定递归函数的参数，定义全局变量二维数组result来记录最终结果，参数n是棋盘的大小，然后用row来记录当前遍历到棋盘的第几层 vector if(row==n){result.push_back(chessboard);return;}最后是确定单层搜索的逻辑，递归深度就是row控制棋盘的行，每一层里for循环的col控制棋盘的列，一行一列，确定了放置皇后的位置。每次都是要从新的一行的起始位置开始搜，所以都是从0开始； for(intcol=0;col boolisValid(introw,intcol,vector 图的m着色问题：给定一个无向连通图G和m种颜色，给图G的所有顶点着色，使得任何两相邻顶点的颜色不同（G可以是平面图，也可以是非平面图） 四色定理：任何平面图都是可以4着色的、 我们这里使用4个顶点、3种颜色说明 voiddfs(intcur){if(cur>n){ans=1;return;}for(inti=1;i<=m;i++){//对cur结点尝试使用每一种颜色进行涂色boolflag=1;//cur之前的结点必被涂色for(intj=1;j 这一章主要针对BUPT王晓茹老师的算法设计与分析课程做一个期末的复习整理，通过前面对常规算法的了解，我们能够轻松掌握考试题型；