注：本文是 BAT 真题收录很值得大家花心思看完，看完会有播种。
前言
算法是面试大公司必考的我的项目，所以面试前筹备好算法至关重要，明天整顿的常见的动静布局题目，心愿能够帮到大家。
要想学习其余绝世武功，要先打好根底。算法属于内功，则更为重要。
匪徒抢劫
题目：匪徒抢劫一排房间，每个房间都有钱，不能抢劫两个相邻的房间，要求抢的钱最多。数组如：[2,7,9,3,1]
思路：当输出房间数为 0,1,2 时，这个很好判断，当输出房间数字大于 3 时，就要用到动静布局了，方程是:
dp[i]是当抢到第 i 个数时，能抢到最大值，从部分最大值推到最终后果最大。
如果抢到第 5 个房间，那么第 5 个房间有二种状况，抢不和不被抢，因为只能隔房间。
如果抢到第 4 个房间，有个最大值；抢到第 3 个房间，有个最大值。
如果加上第 3 房间最大值，加上第 5 房间的最大值，大于抢到第 4 个房间时的最大时。那就抢 3,5 而不抢 4，反而，就按抢 4 的策略。
这样从前往后推，最初的后果肯定是最大的。
代码如下：
跳台阶
题目形容：有 N 阶楼梯，每次可上一阶或两阶，求有多少种上楼梯的办法
先来剖析下这个问题：
当 N = 1 时，这个很好了解，只能跨 1 步这一种了
当 N = 2 时，你每次能够跨 1 步或 2 步，那就是走 2 步或走两个 1 步
当 N = 3 时，因为你能够跨 1 步或 2 步，那你在台阶 1 或 2 都能行。要计算到台阶 1 有多少种走法，到台阶 2 有多少种走法，而后 2 种相加，顺次逆推。
当 N = 4 时，你在台阶 2 或 3 都能行，计算到台阶 2 有多少种走法，到台阶 3 有多少种走法，而后 2 者相加，顺次逆推。
总结如下：你会发现，这是斐波拉切数列，应用递归呈现反复计算问题，所以抉择动静布局算法。
| 层数 | 公式 | 种数 |
|---|---|---|
| 1 | f(1)=1 | 1 |
| 2 | f(2)=2 | 2 |
| 3 | f(3)=f(1)+f(2) | 3 |
| 4 | f(4)=f(2)+f(3) | 5 |
第三层：3 种（在第一层走 2 步或在第二层走 1 步）
第四层：5 种（在第二层走 2 步或在第三层走 1 步）
代码如下：
i,j 首先赋边界值，res 保留 i + j 的值，每次后退，i,j,res 的值都会被赋到后面后果。
下面的算法是底向上，递归相当于自顶向下，防止了反复计算。
矩形最小门路和
题目：
给定一个，蕴含非负整数的 m x n 网格。请找出一条，从左上角到右下角的门路。使得门路上，所有数字总和为最小，每次只能向下，或者向右挪动一步。
输出:[[1,3,1],
[1,5,1],
[4,2,1]]
输入: 7
解释: 因为门路 1→3→1→1→1 的总和最小。
先看动静方程：
| i 值 | j 值 | dp 方程 |
|---|---|---|
| i>0 | j=0 | dpi = dpi−1 + gridi |
| i=0 | j>0 | dp0 = dp0 + grid0 |
| i<0 | j>0 | dpi = min(dpi−1, dpi) + gridi |
阐明：因为 i=0 和 j=0 是临界条件，所以要先求进去。当 i>0 和 j>0 时，看如上数组，5 能够由上方 3，或者左方 1 走过去。
当走 5 的时候，要选取上方 3 对应的 dp，与左方 1 对应的 dp 进行比拟，抉择较小值累加，这样走进去的才是最小值。最初推出，到右下角的最小值。
代码如下：
sum 用来存储，从 0 到 sumi 门路的最小和，看看每次 sum 的变动，sum1= 7 意思是，从 0 到 1 门路最小和是 7。
程序先把，第 2 行对应的 sum 都求进去，再把第 2 列对应的 sum 都求进去，最初求 sum2 就很容易了。
最初，sumi- 1 就是推出的最小值，上述代码就是 dp 方程的实现。
划分数组为两个相等的子集
题目：输出：[1, 5, 11, 5]，输入：[1, 5, 5]和[11]
思路是，绝对数组中每个数求 dp，最初就会找到 dp[target]是否为 true。
如果 dp[j – nums[i]] 为 true 的，阐明能够组成 j-nums[i]这个数，再加上 nums[i]，就能够组成数字 j。
当 j = target 是同样情理，要想找到 dp[target]为 true，就找到数组中，几个值的和为 target 时，对应下标的 dp 值为 true，这样反推 dp[target]为 true。
代码如下：
乘积最大间断子数组
题目：
输出一个整形数组，数组里有负数也有正数。数组中间断的一个，或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值。
例如数组：arr[]={1, 2, 3, -2, 4, -3} 最大子数组为 {1, 2, 3, -2, 4} 和为 8。
思路：fmax(i) 示意，以第 i 个元素结尾的，乘积最大子数组的乘积，fmin(i) 示意，以第 i 个元素结尾的，乘积最小子数组的乘积。
这里分为最大和最小是因为数组可能存在正数，最大值乘以正数变成较小值，最小值乘以一个正数也可能变成最大值。
比拟方程是：以后数乘以上一个最大值，以后值，以后数乘以上一个最小值。这三者比拟，其中的最大值，就是咱们要的最大值。
同样，每次也要把最小值计算出来，形式同上。
代码如下：
等差递加区间的个数
题目：求一个数组中等差递加区间个数，等差数列必须是间断的。
例子：A = [1, 2, 3, 4]，个数为 3，别离是: [1, 2, 3], [2, 3, 4]
等差数列公式：
先看一个表：
| 数组 | 等差数列的数目 | 与上一组等差数列比拟 |
|---|---|---|
| 1 2 3 | 1 | 1 – 0 = 1 |
| 1 2 3 4 | 3 | 3 – 1 = 2 |
| 1 2 3 4 5 | 6 | 6 6 – 3 = 3 |
| 1 2 3 4 5 6 | 10 | 10 – 6 = 4 |
其实仔细观察，发现这是一个斐波拉切数列，0,1….n- 2 数的求和，动静布局找到方程了，就发现非常简单了。
这就是法则，但须要本人去发现法则，有些题目咋看一脸懵逼，认真看就会发现其中的法则。
dp[i] 示意到 i 地位时，子数组的个数。数组长度大于 3。
上面看下代码：
上面再看代码执行值的变动过程：
| i 值 | 子数组 | dp[i] | res |
|---|---|---|---|
| i = 2 | 123 | 1 | 1 |
| i = 3 | 123 234 1234 | 2 | 3 |
| i = 4 | 123 234 1234 2345 12345 | 3 | 6 |
| i = 5 | 123 234 1234 2345 12345 23456 123456 | 4 | 10 |
很显著，就是 0,1….n- 2 数的求和。
最长回文子串
题目：求最长回文子串。输出: “babad”，输入: “bab”。留神: “aba” 也是一个无效答案。
dpi 示意，字符 s 从下标 i 到下标 j，是否为回文串。
如果 bab 是回文串，那么 ababa 也是回文串。因为，在两边减少了雷同的数。同理，能够给出动静方程：
上面看下代码：
这段代码用利用了 dpi + 1，其后面曾经计算出来了。
当 k = 4 时，字符串最长，最初符合条件的回文子串最长。留神整个循环遍历的过程，用 k 最为两个下标的间距，而后遍历每种可能的后果，判断是否回文。
最长的子串最初判断，将符合条件的子串保存起来。动静布局方程揣测极为重要。
最长递增子序列
求一个数组的最长自增子序列。
输出: [10,9,2,5,3,7,101,18]，输入: 4。
解释: 最长的回升子序列是 [2,3,7,101]，它的长度是 4。
代码如下：
dp[i]示意以 a[i]这个元素结尾的最长递增子序列的长度。
想求 dp[5] 的值，也就是想求以 nums[5] 为结尾，其最长递增子序列。
nums[5] = 3，既然是递增子序列。咱们只有找到，后面那些结尾比 3 小的子序列，而后把 3 接到最初，就能够造成新的递增子序列，而且这个新的子序列长度加一。
当然，可能造成很多种新的子序列，然而咱们只有最长的，把最长子序列的长度作为 dp[5] 的值即可。
依据此顺次类推到后面，d[0],d[1]…d[i]都是这样求进去的，看来动静布局有些是逆推的。
最大子序和
给定一个整数数组 nums，找到一个具备最大和的间断子数组（子数组起码蕴含一个元素），返回其最大和。
输出: [-2,1,-3,4,-1,2,1,-5,4]，输入: 6，解释: 间断子数组 [4,-1,2,1] 的和最大，为 6
解决思路：动静布局
动静布局方程：
动静布局：定义 dp[i]示意为 nums[i]为结尾的 [间断子数组的最大和。
当遍历到 nums[i]时，咱们须要比拟 nums[i]和 dp[i-1]+nums[i]谁更大，而后取较大值。
代码如下：
结尾
大厂面试算法是必考题，动静布局是常考的算法，面试务必要把握。心愿大家能找称心的工作。