一、八皇后问题的描述 八皇后问题是一个以国际象棋为背景的问题：如何能够在8×8的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的n皇后摆放问题：这时棋盘的大小变为n×n，而皇后个数也变成n。当且仅当n = 1或n ≥ 4时问题有解。(摘自维基百科) 其实这里是作为我的一个算法练习，在以前的学习中，我曾经使用过GA算法实现过八皇后问题，主要的思路是将八皇后问题转化成为一种组合优化问题
国际象棋8x8的棋盘，皇后棋子的该行，该列，两条对角线上，均不能再放置皇后棋子。那么放置8个皇后，最多有多少种摆法？
（写这篇文章主要是明天就要考试了，算法考试，今天不想再复习了，xiang着今天也开通了博客，于是在这个平台上进行复习，应该会更高效。最后祝愿我明天考个好成绩。嘻嘻。。。） n皇后问题，主要是应用到回溯法。首先选取一条路径进行计算，如果不满足条件则，进行回溯，选择另外的路径进行计算。 我觉得回溯法：就想是在走迷宫，先选取一条路进行走，如果不能走通，就返回，在选择路口的地方，选择其他的路口，如果能走通，就说明路径选择正确。也就是说找到了解决问题的方法。 下面进行代码分析与解决： 问题分析，n皇后问题，问题分析
保持更新，转载请注明出处；更多内容请关注cnblogs.com/xuyaowen;
No.9期 递归——以阶乘为例 Mr. 王：我们介绍一个在计算机算法设计和程序设计中都非常常见的概念——递归。 小可：什么是递归呢？ Mr. 王：从程序设计的角度来说，递归就是一个函数，在它的定义中调用了它本身。从算法的角度来说，递归就是一个算法对于一个输入的求解需要对这个算法在更小输入上求解的情况。 小可：这个说法听起来有点复杂啊。 Mr. 王：我们举个例子来说明吧。你一定听说过有一个数学概念叫作阶乘。 小可：我知道，阶乘就是把一个正整数一直乘以它的值减1，直到乘数为1，比如5!=5×4×3×2×1。推
回溯算法的基本思想是在搜索过程中，对每个可能的步骤都尝试一遍，如果该步骤不行，则回溯到上一步，尝试其他可能的步骤，直到找到解决问题的方案。回溯算法通常用于解决搜索和优化问题，如数独游戏、全排列、组合、子集、棋盘问题等。
理解递归，汉诺塔(Tower of Hanoi)是个很适合的工具，不大不小，作为最开始递归的理解正合适。从而学习各种计算机语言乃至各种编程范式的时候，汉诺塔一般都作为前几个递归实现的例子之一，是入门的好材料。
复杂度分析： 在一般情况下，每一个数都要与之后的数进行匹配，所以匹配次数将与数据量n挂钩，又由于每轮匹配都要进行(n-1)次比较，所以平均时间复杂度为O(n^2)。
动态规划问题，它不叫动态规划算法，因为它不是一种算法，它是一众类型的问题的统称。 我们前面两篇的“递归算法”、“回溯算法”，以及接下来会讲的“贪心算法”等都属于动态规划的范畴。
在之前的文章大家应该也接触到了一些递归的思想，递归的实质就是函数嵌套着函数，在第一个函数运行中间一定会运行多个函数，因此函数退出条件的设置一定要合理，否则会造成堆栈充满，程序异常退出！ 那我们今天来看看如何从暴力递归改成动态规划？动态规划的实质又是什么？什么情况下可以让暴力递归改成动态规划？
动态规划方法通常用来求解最优化问题。 适合使用动态规划求解最优化问题应具备的两个要素： 1、最优子结构：如果一个问题的最优解包含子问题的最优解，那么该问题就具有最优子结构。 2、子问题重叠(如果子问题不重叠就可以用递归的方法解决了) 具备上述两个要素的问题之所以用动态规划而不用分治算法是因为分治算法会反复的调用重叠的子问题导致，效率低下，而动态规划使用了运用了空间置换时间的思想，将每一个已解决的子问题保存起来，这样重复的子问题只需要计算1次，所以时间效率较高。 动态规划算法设计步骤： 1.刻画一个最优解的结
版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.net/ajianyingxiaoqinghan/article/details/79682147
大家好，我是光城。算法在计算机领域的重要性，就不用我多说了，每个人都想要学算法，打牢算法基础，可是不知道如何做，今天我来推荐一波学习思路。
递归的意思就是函数自己调用自己。 但在使用递归时，程序员需要注意定义一个从函数退出的条件，否则会进入死循环。
八皇后问题，一个经典的回溯算法问题。在8*8的国际象棋棋盘上如何才能放上八只皇后棋子，使它们彼此不会互相攻击到。皇后，是能攻击到以自己为中心的横线竖线和正斜线的强大棋子，在这样的棋盘上摆放8个皇后，这个程序就是要解决到底有多少种摆放法。历史上有那么多的大师研究这个问题，而如今利用计算机强大的计算能力，我们遍历一次棋盘——不到5ms的时间——便得到了结果，一共92种。
递归算法是一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法。它通常把一个大型复杂的问题转化为一个与原问题类似的规模较小的问题来求解。
递归算法的核心思想是将求解的问题分解成若干具有相同属性的子问题，通过这些子问题的解得到原问题的解。 递归算法的主要缺陷是在递归调用过程中存在冗余的运算，这将增加算法的时间复杂度和空间复杂度。 动态规划算法可以消除这些冗余的计算。 同贪心算法，动态规划也有递归的影子。
一、 知识点梳理 (一) 先从工具STL说起： 容器学习了：stack，queue，priority_queue，set/multiset，map/multimap，vector。 1.stack： 栈是一种只能在某一端插入和删除数据的特殊线性表。他按照先进先出的原则存储数据，先进的数据被压入栈底，最后进入的数据在栈顶，需要读数据的时候从栈顶开始弹出数据(最后被压入栈的，最先弹出）。因此栈也称先进后出表。 2.queue： 是典型的先进先出容器，FIFO（first-in-first-out），通俗点说就，这个容器就像是在排队，走的人在前面走，来的人在后面排，排队的顺序和离开的顺序是相同的。 3. priority_queue： 优先队列priority_queue可理解为一个大根堆，有特定权值的先出队，也形象的举个例子，拍卖，无论出手多晚，只要出价足够高，就可以拿走拍卖品。(但是，在优先队列里，元素排列绝对不是完全单调的，只能确定队首元素是最大的，保证出队顺序是单调的) 4.vector： 简单地说，vector是一个能够存放任意类型的动态数组，能够增加和删除数据，可以直接访问向量内任意元素。 5. set/multiset： 两容器相似，但set为有序集合，元素不能重复，multiset为有序多重集合，可包含若干相等的元素，可以放结构体，但是一定要重载排列方式，不然编译都过不了，set的查找于插入元素的复杂度为log(N),是一个比较好用的容器。 PS：但是，在使用结构体时，有几个元素，就要写几个元素的比较，不然会被视为同一个元素： 6.map/multimap：map映射容器的元素数据是由一个Key和一个Value成的，key与映照value之间具有一一映照的关系。map插入元素的键值不允许重复，类似multiset，multimap的key可以重复。比较函数只对元素的key进行比较，元素的各项数据只能通过key检索出来。虽然map与set采用相同的数据结构，但跟set的区别主要是set的一个键值和一个映射数据相等，Key=Value。就好像是set里放的元素是pair组成了map，map的key也可以为自定义数据类型，但是也要像上文set一样写重载函数。 算法（algorithm）：在算法头文件下包括了好多函数，下面列出常用的。
给定一定楼层数的建筑物和一定数量的鸡蛋，求出可以找出门槛楼层的最少鸡蛋掉落实验的次数，约束条件是：幸存的鸡蛋可以重复使用，破碎的鸡蛋不能再次使用，如果鸡蛋从此层掉落会碎，那么从更高的楼层掉落也会碎，如果鸡蛋从此层掉落不会碎，那么从更低的楼层掉落也不会碎。
任何一个可以用计算机求解的问题所需的计算时间都与其规模n有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少。 分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。 如果原问题可分割成k个子问题（1＜k≤n），且这些子问题都可解，并可利用这些子问题的解求出原问题的解，那么这种分治法就是可行的。 由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。
一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
动态规划进阶篇1—-背包问题 大家好，这次给大家分享的题会比以往难一点， 学会了这道题的解题思想，对动态规划的掌握 就更上一层楼了 下面先给大家讲有关于动态规划的两个概念（其实在上两次的题中我们一直有
你可以将其视作是由递归公式定义的数字字符串序列：countAndSay(1) = "1" countAndSay(n) 是对 countAndSay(n-1) 的描述，然后转换成另一个数字字符串。
回溯法的基本思想是采用递归和深度优先搜索的方法，尝试在一组可能的解中搜索出符合要求的解，在搜索过程中，若发现当前所选的方案不能得到正解，就回溯到前面的某一步（即撤销上一次的选择），换一种可能性继续尝试，直到找到符合要求的解或者所有的可能性都已尝试完毕。
前言 作为一个退役狗跟大家扯这些东西，感觉确实有点。。。但是，针对网上没有一篇文章能够很详细的把动态规划问题说明的很清楚，我决定还是拿出我的全部家当，来跟大家分享我对动态规划的理解，我会尽可能的把所遇到的动态规划的问题都涵盖进去，博主退役多年，可能有些地方会讲的不完善，还望大家多多贡献出自己的宝贵建议，共同进步~~~ 概念 首先我们得知道动态规划是什么东东，百度百科上是这么说的，动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数
欧几里得算法是用来求解两个不全为0的非负整数m和n的最大公约数的一个高效且简单的算法。该算法来自于欧几里得的《几何原本》。数学公式表达如下：
每年一到要找工作的时候，我就能收到很多人给我发来的邮件，总是问我怎么选择他们的offer，去腾讯还是去豆瓣，去外企还是去国内的企业，去创业还是去考研，来北京还是回老家，该不该去创新工场？该不该去 thoughtworks？……等等，等等。今年从7月份到现在，我收到并回复了60多封这样的邮件。我更多帮他们整理思路，帮他们明白自己最想要的是什么。（注：我以后不再回复类似的邮件了）。 我深深地发现，对于我国这样从小被父母和老师安排各种事情长大的人，当有一天，父母和老师都跟不上的时候，我们几乎完全不知道怎么去做选
每年一到要找工作的时候，我就能收到很多人给我发来的邮件，总是问我怎么选择他们的 offer，去腾讯还是去豆瓣，去外企还是去国内的企业，去创业还是去考研，来北京还是回老家，该不该去创新工场？该不该去 thoughtworks？……等等，等等。今年从 7 月份到现在，我收到并回复了 60 多封这样的邮件。我更多帮他们整理思路，帮他们明白自己最想要的是什么。（注：我以后不再回复类似的邮件了）。 我深深地发现，对于我国这样从小被父母和老师安排各种事情长大的人，当有一天，父母和老师都跟不上的时候，我们几乎完全不知
每年一到要找工作的时候，我就能收到很多人给我发来的邮件，总是问我怎么选择他们的 offer，去腾讯还是去豆瓣，去外企还是去国内的企业，去创业还是去考研，来北京还是回老家，该不该去创新工场？该不该去 t
每年一到要找工作的时候，我就能收到很多人给我发来的邮件，总是问我怎么选择他们的offer，去腾讯还是去豆瓣，去外企还是去国内的企业，去创业还是去考研，来北京还是回老家，该不该去创新工场？该不该去thoughtworks？……等等，等等。今年从7月份到现在，我收到并回复了60多封这样的邮件。我更多帮他们整理思路，帮他们明白自己最想要的是什么。（注：我以后不再回复类似的邮件了）。 我深深地发现，对于我国这样从小被父母和老师安排各种事情长大的人，当有一天，父母和老师都跟不上的时候，我们几乎完全不知道怎么去做选择
信息学奥赛作为计算机科学领域的一项重要竞赛，旨在锻炼学生的计算思维能力、算法设计和编程技能。在这项竞赛中，合理选择编程语言是成功的关键因素之一。C++作为一种功能强大、灵活性高的编程语言，广泛应用于信息学奥赛中，不仅因为其丰富的数据结构和算法支持，还因为其能够在竞赛环境下实现高效的解决方案。
今天是LeetCode专题第63篇文章，我们一起来聊聊LeetCode中的第98题，二叉搜索树的合法性判断问题。和之前介绍过的几道题类似，也是一道关于二叉搜索树的问题。
分治法，顾名思义分而治之的意思，就是把一个复杂的问题分成两个或很多其它的同样或相似的子问题，再把子问题分成更小的子问题……直到最后子问题能够简单的直接求解，原问题的解即子问题的解的合并。
由于要求所有的可能性，因此考虑使用回溯法进行求解。回溯是一种通过穷举所有可能情况来找到所有解的算法。如果一个候选解最后被发现并不是可行解，回溯算法会舍弃它，并在前面的一些步骤做出一些修改，并重新尝试找到可行解。究其本质，其实就是枚举。
程序与算法的区别：程序可以不满足算法的第四点性质即有限性。例如操作系统，是在无限循环中执行的程序。
三元素集{a,b,c}的子集是：{},{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}。 这些子集又可以使用01序列来表示，分别是000,100,010,001,110,101,011,111。 0/1分别代表着 含有/不含 原集合中的对应元素。
八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。计算机发明后，可以快速解决此类问题。
多重幂计数就是指数塔的组合最优解问题，设给定的n个变量X1，X2，...，Xn。将这些变量依序作底和各层幂，可得n重幂如下：
mod 1234 (3)计算 gcd(57,93)，并找出整数s和t，使得57s+93t=gcd(57,93) (4）求解下列同余方程组
汉诺塔是很简单也很经典的算法之一。 汉诺塔是根据一个传说形成的数学问题： 有三根杆子A，B，C 。A杆上有N个(N>1)穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆：
力扣78. 子集 题目描述： 给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。 示例 1： 输入：nums = [1,2,3] 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]] 示例 2： 输入：nums = [0] 输出：[[],[0]] 提示： 1 <= nums.length <= 10 -10 <= nums[i] <= 10 nums 中的
动态规划英文 Dynamic Programming，是求解决策过程最优化的数学方法，后来沿用到了编程领域。
https://leetcode-cn.com/problems/subsets-ii
4.使用循环从1到rest（即剩余数字n）遍历cur，cur为当前需要划分的数字。
有两个数 a b，现在，我们要求 a b 的最大公约数，怎么求？枚举他们的因子？不现实，当 a b 很大的时候，枚举显得那么的naïve ，那怎么做？
在nxn格的棋盘上放置彼此不受攻击的n格皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在nxn格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。
由于这次考试太仓促，往届真题搞到了，答案没搞到、更别说挤时间自己去做一份正常答案了。这些反复考的题目，的确有点让人反胃，相反，有一道全新的题目，让我眼前一亮，可我愣是苦思冥想了两天不得其解，网上也没能找到答案，这不，就来分享给大家了。
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
回溯法(探索与回溯法)是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
数据结构决定了数据存储的空间和时间效率问题，数据的写入和读取速度也决定了应该选择怎样的数据结构
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
ICP备案
实时音视频
即时通信 IM
对象存储
