大厂动态规划面试汇总,教你如何修炼内功
前言
算法是面试大公司必考的项目,所以面试前准备好算法至关重要,今天整理的常见的动态规划题目,希望可以帮到大家。
要想学习其他绝世武功,要先打好基础。算法属于内功,则更为重要。
强盗抢劫
题目:强盗抢劫一排房间,每个房间都有钱,不能抢劫两个相邻的房间,要求抢的钱最多。数组如:[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)=11 1
2 f(2)=2 2
3 f(3)=f(1)+f(2) 3
4 f(4)=f(2)+f(3) 4
第三层: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 - 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]谁更大,然后取较大值。
代码如下:
结尾
大厂面试算法是必考题,动态规划是常考的算法,面试务必要掌握。希望大家能找满意的工作。
专注后台开发相关技术,广度深度并存,干货情怀同在。
微信搜索【晨梦思雨】关注这个不一样的程序员。
版权声明: 本文为 InfoQ 作者【Kevin】的原创文章。
原文链接:【http://xie.infoq.cn/article/14f7f218c225aabd78938b726】。文章转载请联系作者。
评论