前言

动态规划也是编程面试中的常考题。如果所求问题是求最优解，而且问题能够分解为若干个子问题，并且子问题之间还有重叠的更小的子问题，那么应该考虑应用动态规划思想求解。

在应用动态规划之前要分析能否把大问题分解成小问题，分解的每个小问题也存在最优解。如果把小问题的最优解组合起来能够得到这个问题的最优解，那么我们就可以应用动态规划解决这个问题。

总之，动态规划存在以下几个特点：

1. 目标问题是求最优解；
2. 整体的最优解可以由子问题的最优解参与或组合得到；
3. 大问题可以分成若干个子问题，且子问题之间还有相互重叠的更小的子问题；
4. 为避免重复求解子问题(后面求大问题的时候可能多次用到)，采用自下而上的顺序先计算小问题的最优解并记录到一维或二维数组中，再根据已经解出的小问题来求出大问题的最优解。简而言之，就是自上而下分析问题，自下而上求解问题。

题目(剪绳子)

题目：给定一根长度为n的绳子，请把绳子剪成 m 段(m,n 都是整数且均大于 1，至少剪一刀)，每段绳子的长度记为 k[0],k[1],…,k[m]。请问 k[0]xk[k1]x…xk[m] 可能的最大乘积是多少？例如，绳子长度为 8，可分成 2，3，3，三段，最大乘积为 18。

解题思路

动态规划法

首先定义函数 f(n) 为把长度为 n 的绳子剪成若干段后的最大乘积值。
剪绳子求的是最大乘积值满足特点 1；如果在绳子的 i 处剪一刀，那么 f(n) 要达到乘积最大，则 f(i)与 f(n-i) 也要达到乘积最大，满足特点 2；假设 n=6，那么 f(2) 和 f(4) 都是问题的子问题，但其实 f(2) 也是 f(4) 的子问题，那么就出现了重叠的更小的子问题，满足特点 3；所以，我们为了求解目标问题，都是先从小问题开始求解，即自下而上求解，并将每个子问题的乘积最大值记录到数组中备查，满足特点4。因此，本题的确适合采用动态规划求解。

当绳子长度为 2 的时候，只能剪成两段长度为 1，所以 f(2)=1；当绳子长度为 3 的时候，有两种剪法，其中最大的 f(3)=2。

那么当 n>4 的时候，我们要求出把长度为 i 的绳子剪成若干段之后各段长度乘积的最大值，即求 f(i)，而4<=i<=n，即要求出所有子问题的最优解。那么对于每个子问题 f(i)，由于可以有 i/2 种切法，所以我们应该遍历每种切法，并计算出乘积最大的那种切法。当切点在 j(1<=j<=i/2) 处时，子问题 f(i)=max(f(j)xf(i-j)),其中 f(j),f(i-j)，都可以从备忘数组中查询得到。

贪心算法

即选择一个能够得到乘积最大值的策略进行。当 n>=5 时，我们尽可能的剪出长度为 3 的小绳子；当剩下的绳子长度为 4 时，改为把绳子剪成两段。
证明 :首先，当 n>=5 时，我们可以证明 2(n-2)>n 并且 3(n-3)>n。也就是说，当绳子剩下的长度大于或者等于 5 的时候，我们就把它剪成长度为 3 或者 2 的绳子段。另外，当 n>=5 时，3(n-3)>=2(n-2)，因此我们应该尽可能地多剪长度为3的绳子段。而当 n=4 时，由于 2x2>1x3 所以应该剪成两条长度分别为 2 的绳子段。

算法实现

动态规划实现

贪心算法实现

复杂度分析

对于动态规划法，两层循环，时间复杂度为 O(n^2)，另外，建立了辅助容器，空间复杂度为 O(n)；对于贪心算法，复杂度均为 O(1)。

参考

<<剑指offer2>>

前言

机器人的运动范围仍然和前一篇的寻找矩阵路径相似，都是在一个给定的网格内搜索问题的解，因此思路大体一致，还是利用回溯法来进行求解。

题目(机器人的运动范围)

题目：地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为 18 时，机器人能够进入方格（35,37），因为 3+5+3+7 = 18。但是，它不能进入方格（35,38），因为 3+5+3+8 = 19。请问该机器人能够达到多少个格子？

解题思路

虽然本题不是给定一个矩阵进行搜索，但是它给定了可以搜寻的网格边界，因此还是类似矩阵搜索问题解的办法。
首先本题进入格子的条件基本和前一篇相似，只是字符串可以匹配换成了行坐标和列坐标的数位之和小于等于 k。然后，机器人每进入一个格子之后，它可以继续向该格子的左、右、上、下移动一格，所以我们依然只需递归下去求解，并返回递归结束后的格子数即可。也就是说，能进入的格子总数=当前格子(1) + 来自上下左右递归后返回的计数。

算法实现

复杂度分析

时间复杂度

时间复杂度 O(rowsxcols)。

空间复杂度

建立了一个辅助空间布尔矩阵，空间复杂度为 O(rows*cols)。递归工作栈消耗 O(max(rows,cols))。

参考

<<剑指offer2>>

前言

回溯法可以看成蛮力法的升级版。它会搜遍问题的解空间，试图找到一个符合约束条件的解决方案。回溯法非常适合由多个步骤组成的问题，并且每个步骤都有多个选项。当我们在某一步选择了一中一个选项时，就进入下一步，然后有面临新的选项。我们就这样重复选择，直至到达最终的状态。

而这样的选择过程非常适合用树结构来表示。在某一步有 n 个可能的选项，那么把该步骤看出树状结构中的一个节点，每个选项就看出树中节点连接线，经过这些连接线到达该节点的 n 个子节点，再选定符合的子节点到达下一步骤。树的叶节点对应着终结状态。如果叶节点的状态满足题目的约束条件，那么我们找到了一个可行的解决方案。

如果在叶节点的状态不满足约束条件，那么需要回溯到上一节点再尝试其他的选项。如果上一节点所有可能的选项都已经尝试过，仍满足不了题目的约束条件，则再次回溯到上一节点。如果所有选项都已经尝试过仍然不能到达满足约束条件的终结状态，则该问题无解。

题目(矩阵中的路径）

题目：请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 例如 a b c e s f c s a d e e 矩阵中包含一条字符串”bcced”的路径，但是矩阵中不包含”abcb”路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。

解题思路

首先，由于可以在矩阵中任意选择一个格子作为路径的起点，因此首先应该遍历矩阵的每个位置作为可能的起点。然后，假设矩阵中的某个格子上的字符为ch，并且字符串的第 i 个位置也为字符 ch，那么就到相邻的格子寻找字符串中第 i+1 位置上的字符。如果该格子上的字符与字符串的第i个路径上的字符不同，则跳过该格子。重复以上过程，直至字符串中的字符都在矩阵中相应位置出现。另外，需要定义 bool 矩阵标识路径是否已经进过每个格子。

当矩阵中坐标为(row,col)的格子和路径字符串中下标为pathLength的字符一样时，从4个相邻的格子(row,col-1),(row-1,col),(row,col+1)和(row+1,col)中去定位字符串中下标为pathLength+1的字符。
如果都没有匹配到，则需要回到前一个字符(pathLength-1)，重新定位。

重复这个过程，直到遇到’\0’。

算法实现

复杂度分析

时间复杂度

首先hasPath中有两层循环，耗时O(rowsxcols),接着每个格子最多需要判断周围 4 个格子是否为路径的下一个字符，时间复杂度O(4xrowsxcols)。因此最后的时间复杂度为O(rows^2xcols^2)。可能分析的不是很对，请指教。

空间复杂度

建立了一个辅助空间布尔矩阵，空间复杂度为O(rowsxcols)。假设字符长度为n，则递归栈需要O(n)的空间，但最大的复杂度还是O(rowsxcols)。

参考

<<剑指offer2>>

前言

查找和排序是在程序设计中经常用到的算法。查找相对而言不外乎顺序查找、二分查找、哈希表查找和二叉排序树查找，因此只要我们掌握了这些查找技巧，然后在面对不同问题的时候就可以选择合适的查找方法解决。最重要的是，二分查找是面试时候的重点，也是面试官最喜欢考查的查找方式。

哈希表和二叉排序树查找的重点在于构建对应的数据结构而不是算法本身。哈希表主要的优点是可以在 O(1) 的时间内查找某一元素，是效率最高的查找方式，而其缺点必然是消耗额外的空间来实现哈希表。
最后，我们应该要熟练掌握插入排序、冒泡排序、归并排序和快速排序算法的实现并能比较算法之间的优劣，能够从空间复杂度、平均时间复杂度和最差时间复杂度等方面去比较它们的优缺点。

题目(旋转数组)

题目：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组{3，4，5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小元素为1。

算法思路

为了能够充分利用旋转数组的特性，我们肯定不能采用 O(n) 时间复杂度的方式去遍历数组得到最小的那个元素(顺序查找)，那么旋转数组的特性是什么？ 其一是旋转后的数组一般可以划分为两个递增有序的子数组，并且前一个子数组的元素都大于后面子数组的元素；其二是最小的元素刚好是这两个子数组的分界线。那么可以考虑利用二分查找来缩小查找的范围。具体如下：

1. 情况一：当搬运的若干个元素为0时，意味这旋转数组仍为原排序数组，那么最小的元素肯定是第一个元素；
2. 情况二：我们给排序数组两个指针，一个指向首元素，另一个指向尾元素，接着取中点，然后先判断首元素和中点元素以及尾元素是否相等，如果相等，那么我们此时我们无法知道两个子数组谁一定会比谁更大，因此我们只能采用顺序查找的方式来返回最小的元素；否则，我们判断中点元素的值是否比首元素大，如果大，那么说明前面的子数组必定大于后面的子数组，最小值肯定在后面的子数组中，那么此时将指向首元素的指针移动到中点元素，缩小查找的范围，然后继续二分查找；如果小，那么原理相反，只需要把指向尾元素的指针移动到中点元素，继续二分查找即可。
3. 进入二分查找的条件：二分查找数组的首元素大于其尾元素。这样说明有大于0个的元素被搬到了后面。
4. 二分查找的结束条件：当首指针和尾指针位置相邻的时候，尾指针指向的元素即为最小的元素，此时退出循环即可。

下图为首元素、中点元素和尾元素都相等的情况(阴影部分为其中一个子数组，这种特例对于二分查找失效)：

算法实现

复杂度分析

时间复杂度

当旋转数组仍为排序数组的之后，直接去第一个元素，时间复杂度O(1)；当旋转数组采用顺序查找的时候，时间复杂度为O(n)；当旋转数组采用二分查找的时候，时间复杂度为O(logn)，所以最好的时间复杂度为O(1)，最坏时间复杂度为O(n)。

空间复杂度

空间复杂度为O(1)。

参考

<<剑指offer2>>

前言

不同排序算法适用的场合也不尽相同。例如，对于数组有序的情况，使用快速排序算法将达到最坏的时间复杂度O(n^2)，那么此种场合下，快速排序算法就不是最优的选择。因此，选择一个排序算法，应当考虑到排序应用的环境、哪些约束条件(比如数据的范围)，最后综合考虑后选择相应的排序算法解决。

题目(年龄排序)

请实现一个按年龄排序的算法，其中最大年龄为99岁，要求时间效率为 O(n)(可以使用不超过O(n)的辅助内存)

算法思路 (排序对象有范围限制)

我们看到题目要求的排序时间复杂度要达到 O(n),而那些常见排序算法的最坏时间复杂度基本都达不到 O(n)。我们注意到排序的对象是年龄，它是有约束的，即年龄只能在0-99岁之间。那么，我们可以利用辅助数组来记录每个年龄有多少人次(数组的下标即年龄)，那么我们对年龄进行排序的时候，只需要遍历所有年龄，得到相应的人次，然后给年龄数组重新赋值即可。

算法实现

参考

<<剑指offer2>>