剑指offer（专项突破版）15.2 图的搜索LCR105.岛屿的最大面积可以逐一扫描矩阵中的每个格子，如果遇到一个值为1的格子并且它不在之前已知的岛屿上，那么就到达了一个新的岛屿，于是搜索这个岛屿并计算它的面积。在比较所有岛屿的面积之后就可以知道最大的岛屿的面积。 广度优先广度优先搜索通常需要一个队列。先将起始节点添加到队列中。接下来每步从队列中取出一个节点进行访问。 1234567891011

剑指offer（专项突破版）14.5 背包问题LCR101.分割等和子集分析如果能够将数组中的数字分成和相等的两部分，那么数组中所有数字的和（记为sum）应该是一个偶数。也可以换一个角度来描述这个问题：能否从数组中选出若干数字，使它们的和等于sum/2（将sum/2记为t）。如果将数组中的每个数字看成物品的重量，也可以这样描述这个问题：能否选择若干物品，使它们刚好放满一个容量为

剑指offer（专项突破版）14.4 矩阵路径问题LCR098.不同路径分析可以用函数f（i，j）表示从格子的左上角坐标为（0，0）的位置出发到达坐标为（i，j）的位置的路径的数目。如果格子的大小为m×n，那么f（m-1，n-1）就是问题的解。 当i等于0时，机器人位于格子最上面的一行，机器人不可能从某个位置向下走一步到达一个行号i等于0的位置。因此，f（0，j）等于1，即机器人只有一种方法可以到

剑指offer（专项突破版）14.3 双序列问题LCR095.最长公共子序列分析由于输入有两个字符串，因此状态转移方程有两个参数。用函数f（i，j）表示第1个字符串中下标从0到i的子字符串（记为s1[0..i]）和第2个字符串中下标从0到j的子字符串（记为s2[0..j]）的最长公共子序列的长度。如果第1个字符串的长度是m，第2个字符串的长度是n，那么f（m-1，n-1）就是整个问题的解。 如果第

剑指offer（专项突破版）14.2 单序列问题LCR089.打家劫舍分析小偷一次只能进入一幢房屋内盗窃，因此到街道上所有房屋中盗窃需要多个步骤，每一步到一幢房屋内盗窃。由于这条街道有报警系统，因此他每到一幢房屋前都面临一个选择，考虑是不是能进去偷东西。完成一件事情需要多个步骤，并且每一步都面临多个选择，这看起来是一个适合运用回溯法的问题。但由于这个问题并没有要求列举出小偷所有满足条件的偷盗的方法

剑指offer（专项突破版）14.1 动态规划的基础知识和适合运用回溯法的问题类似，适用动态规划的问题都存在若干步骤，并且每个步骤都面临若干选择。如果题目要求列举出所有的解，那么很有可能需要用回溯法解决。如果题目是求一个问题的最优解（通常是求最大值或最小值），或者求问题的解的数目（或判断问题是否存在解），那么这个题目有可能适合运用动态规划。 分治法也是采用递归思路把大问题分解成小问题。例如，快速排

剑指offer（专项突破版）13.3 使用回溯法解决其他类型的问题LCR085.括号生成分析如果输入n，那么生成的括号组合包含n个左括号和n个右括号。因此生成这样的组合需要2n步，每一步生成一个括号。每一步都面临两个选项，既可能生成左括号也可能生成右括号。由此来看，这个问题很适合采用回溯法解决。 在生成括号组合时需要注意每一步都要满足限制条件。第1个限制条件是左括号或右括号的数目不能超过n个。第2

研一小记今天考完试了，我的研一生活基本上算是结束了。最近复习得很累，连说话打字的力气都没有了。算法题从上周一开始复习后就没有再刷了，明天要捡起来了。这周把这些作业写完，方案出出来，下周要开始学自己想学的东西了。 没想到研究生生活是这样的，不知道该从何说起。好像，一年前，我还是坚定读博的，现在，只想能赶紧毕业了。 感受到时间流逝，就会感受到自己什么都没学会，一点长进都没有，还养成了一堆坏习惯。我总是

剑指offer（专项突破版）13.2 集合的组合、排列LCR079.子集分析如果集合中共有 n 个元素，那么确定集合的子集共需要 n 步。每一步都需要从集合中取出一个元素，这时候存在两个选择，添加当前数字或者不添加。生成一个子集需要若干步，并且每一步都有若干种选择，这是应用回溯法的典型问题。 递归函数helper一共有4个参数。第1个参数是数组nums，它包含输入集合的所有数字。可以逐一从集合中取

剑指offer（专项突破版）12 排序LCR074.合并区间分析如果先将所有区间按照起始位置排序，那么只需要比较相邻两个区间的结束位置就能知道它们是否重叠。如果区间1的结束位置大于区间2的起始位置，说明存在重叠，取较大的结束位置。如果它们重叠就将它们合并，然后判断合并的区间是否和下一个区间重叠。重复这个过程，直到所有重叠的区间都合并为止。 12345678910111213141516171819