笔记-100层楼摔2个苹果?动态规划框架
一道经典题
面试的过程也是补全自己的过程,要正视自己的缺点,补足落下的知识,虚心求教,终身学习。
来源:百度面试,Google面试题
题目
有一栋100层高楼,从某一层开始扔下的苹果刚好摔坏,现有两个苹果,试用最简便的方法确定这个恰好摔坏苹果的那层。
一幢 100 层的大楼,给你两个鹰蛋。如果在第 n 层扔下鹰蛋,鹰蛋不碎,那么从第 n-1 层扔鹰蛋,都不碎。这两只鹰蛋一模一样,不碎的话可以扔无数次。最高从哪层楼扔下时鹰蛋不会碎?
- 如果有无数个鹰蛋,如何求解?
- 如果只有两个鹰蛋,如何求解?
不成熟的思考
我给出的解答是进行分段,第一个球每10层进行摔,在第n个十层摔碎后,第二个球从第n-1个十层开始从小到大遍历摔,就可以确定恰好摔坏苹果的那层。二分法风险大。
这个思路是结果导向,这是不对的:只确定了恰好摔坏苹果的那层,最坏情况是测试18次。应该详细分析,进行归纳。
有无数个蛋
这意味着有无数次试错机会,可以用二分法O(logn)的次数内求解问题。
如果只有两个蛋
把楼层等分试探求解
把楼层分为x等分,用第一蛋从上往下一次试探一个范围,如果第一个鹰蛋破了,则用另一鹰蛋穷举。
假设把总楼层分成了x
等分,每个等分内部有n/x
个楼层。在最坏情况下,第一个蛋需要试探x
次,第二个蛋则要试探n/x-1
次(即在每个等分内做穷举),所以最坏的情况需要的总次数为x+(n/x)-1
。
要获取最坏情况的最小值,需要对总次数x+(n/x)-1
求导数,并取0值,求解可以得x=sqrt(n)
。
(x + n/x -1)’
= 1-(n/x^2)
= 0
解得x=sqrt(n)。
在楼层为100的情况下,可以求出使总次数最小的x=10。也就是采用等分的办法,在楼层总数是100时,10等分时最优情况。
动态规划
假设有m
楼层,n
个鹰蛋,则在第i
层试探时会出现两种状态:1. 鹰蛋摔破了,则我们下一步只有n-1
个鹰蛋,同时总楼层数也缩减为i-1
(因为上面的层数可以直接舍去);2. 鹰蛋没有摔破,那么鹰蛋总数不变,还是n
个,楼层数则缩减为m-i
层。
递归在以下三个状态结束:
- 如果鹰蛋只剩1个,那么只能对所有的楼层进行穷举;
- 如果楼层是0,那么试探0次;
- 如果楼层是1,那么试探1次。
状态转移方程:F(m,n) = MAX{F(i-1,n-1)+1, F(m-i,n)+1};(0<i<m)
在C#中的实现:
public class Solution { |
动态规划
定义
动态规划(Dynamic Programming,简称DP)是运筹学的一个分支,它是解决多阶段决策过程最优化的一种数学方法。把多阶段问题变换为一系列相互联系的的单阶段问题,然后逐个加以解决。
这里提到动态规划其实是一种数学方法,是求解某类问题的一种方法,而不是一种特殊的算法,没有一个标准的数学表达式或明确定义的一种规则。
总结起来就是一句话:大事化小,小事化了。
具体来说,动态规划的流程为:暴力的递归解法 -> 带备忘录的递归解法 -> 迭代的动态规划解法。
就思考流程来说:找到状态和选择 -> 明确dp数组/函数的定义 -> 寻找状态之间的关系。
递归方法
1. 问题建模
每一个步骤中,进行分状态定义,再利用递归简化。动态规划当中包含三个重要的概念:最优子结构、边界、状态转移公式。
2. 求解问题
拿一个递归方法举例:
// 求解n=8时,Fun返回值 |
用递归的思路直接做,这是一颗二叉树,树的节点个数就是递归方法需要计算的次数(图中最后一步省略了)。这棵二叉树高度是n-1
节点个数接近·2^(n-1)
,时间复杂度近似看成O(2^n)。
备忘录算法
可以看到上方的递归图有些相同的参数被重复计算了,例如中间的两个Fun(3),这样越往下走,重复的越多。优化方式可以用缓存,创建一个哈希表,每次将不同参数结果存入,遇到相同参数时,从哈希表中取出即可。这个方法叫做备忘录算法。 +
// 求解num=8时,Fun返回值 |
集合map是一个备忘录,每次需要计算F(n)的时候,会首先从map中寻找匹配元素,如果存在就直接返回结果,不存在就计算结果,存入备忘录中。时间复杂度和空间复杂度都是O(n)。
动态规划
上面那个备忘录算法当然不是真正的动态规划实现,可以进一步减小空间复杂度。思路逆转,不对F(n)自顶向下做递归,而是自底向上用迭代。每一次迭代过程中,只要保留之前的两个状态,就可以推导出新的状态。
public int Fun(int n) |
练习
动态规划解题套路框架
动态规划问题的一般形式就是求最值,例如求最长递增子序列,最小编辑距离等。
求动态规划的核心问题是穷举。这类问题存在重叠子问题,具备最优子结构,需要正确的状态转移方程。一般来说,写出状态转移方程是最困难的。
思考框架:明确base case,明确状态,明确选择,定义dp数组/函数的含义。
代码框架:
# 初始化 base case |
斐波那契数列
斐波那契数,通常用
F(n)
表示,形成的序列称为斐波那契数列。该数列由0
和1
开始,后面的每一项数字都是前面两项数字的和。也就是:
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.给定
N
,计算F(N)
。示例 1:
输入:2
输出:1
解释:F(2) = F(1) + F(0) = 1 + 0 = 1.示例 2:
输入:3
输出:2
解释:F(3) = F(2) + F(1) = 1 + 1 = 2.示例 3:
输入:4
输出:3
解释:F(4) = F(3) + F(2) = 2 + 1 = 3.提示:
- 0 ≤
N
≤ 30
暴力递归
int fib(int N) |
根据上方的递归方法,可以画出递归树,能够看出比较低效。时间复杂度为:子问题的个数 乘以 解决一个子问题需要的时间。子问题个数是递归树中节点的总数O(2^n),解决子问题的时间是加法O(1),总时间为两者相乘O(2^n)。可以看到递归树中有大量重复的计算,这就是动态规划问题的第一个性质:重叠子问题。
带备忘录的递归
根据上方的备忘录算法,添加一个哈希表,直接将答案拿来用(空间换时间)。
int fib(int N) |
带备忘录的递归算法,把一颗存在巨量冗余的递归树“减枝”,极大减少了子问题的个数。时间复杂度是O(n)。这种方法叫做自顶向下,而动态规划叫自底向上。
自顶向下是像我们画递归树一样,从要求的大问题向下分解为小问题。而自底向上是从小问题开始往上推,直到推到我们想要的答案。这也就是动态规划一般脱离递归,而由循环迭代完成的原因。
dp数组的迭代解法
我们把这个备忘录独立出来成为一张表,叫做DP table,在这张表上完成自底向上即可。
int fib(int N) |
实际上就是反过来算剪枝的结果。
状态转移方程
实际上是描述问题结构的数学形式:
把F(n)
想做一个状态 n
,这个状态 n
是由状态 n - 1
和状态 n - 2
相加转移而来,这就叫状态转移。
可以看出,上面几种解法中的所有操作,例如 return f(n - 1) + f(n - 2)
,dp[i] = dp[i - 1] + dp[i - 2]
,对备忘录或DP表的初始化,都是这个额方程式的不同表现形式。因此,状态转移方程是解决问题的核心,且直接代表暴力解法。动态规划问题最困难的就是写出这个暴力解(状态转移方程),接下来优化方法无非是用备忘录或者DP table。
状态压缩
可以看出,根据斐波那契数列的状态转移方程,当前状态只和前两个状态有关,并不需要那么长的一个DP table来存储所有状态,只要想办法存储之前的两个状态就行了。可以进一步优化,把空间复杂度降为O(1):
int fib(int n) |
凑零钱问题
题目:给出k
种面值的硬币,面值分别为c1,c2...ck
,每种硬币的数量无限,再给一个总金额amount
,问最少需要几枚硬币凑出这个金额,如果不可能凑出,返回-1。方法声明如下:
// coins中是可选硬币面值,amount是目标金额 |
例:当k = 3
,面值为1,2,5,总金额amount = 11
。那么最少需要3枚硬币凑出,即11=5+5+1。
计算机如何解决这个问题?把所有可能的凑硬币方法琼剧出来,然后找找看最少需要多少枚硬币。
暴力递归
这个问题是动态规划问题,因为具有最优子结构,即子问题间相互独立:如果想求amount = 11
的最少硬币数,只要求出amount = 10
的数量,再加1即可(添加一枚面值1的硬币)。因为硬币数量是没有限制的,所以子问题之间没有限制,是相互独立的。
如何列出正确的状态转移方程?
- 确定base case:目标金额
amount = 0
时算法返回0; - 确定状态,也就是原问题和子问题中会变化的变量。由于硬币数量无限,硬币面额也是给定的,只有目标金额会不断向base case靠近,因此唯一的状态就是目标金额
amount
。 - 确定选择,也就是导致状态产生变化的行为。目标金额变化的原因是在选择硬币,每选择一枚硬币,就相当于减少了目标金额。选择硬币的面额,就是选择。
- 明确
dp
函数/数组的定义。暴力递归是自顶向下的解法,所以会有递归的dp
函数,一般来说函数的参数就是状态转移中会变化的量,也就是状态;函数的返回值就是我们要计算的量。因此我们可以这样定义:
dp(n)
的定义:输入一个目标金额n
,返回凑出目标金额n
的最少硬币数量。
def coinChange(coins: List[int], amount: int): |
数学形式的状态转移方程:
至此暴力法解决,时间复杂度为O(k*n^k),指数级别。
public class Solution { |
带备忘录递归
public class Solution { |
还是很慢,时间复杂度O(kn)。
dp数组的迭代解法
主要问题是确定dp数组的定义:当目标金额为i
时,至少需要dp[i]
枚硬币凑出。
根据开头的动态规划代码框架可以写出:
public class Solution { |
dp
初始化成amount+1
的原因是,凑成amount
金额的硬币数最多只可能等于amount
(也就是全用1元),所以初始化为amount+1
相当于正无穷,可以取最小值。
总结
计算机解决问题的办法就是穷举,算法设计是先思考“如何穷举”,再追求“如何聪明地穷举”。列出状态转移方程就是解决“如何穷举”,备忘录、DP table就是在追求“如何聪明地穷举”。无非是空间换时间。
阅读题目时,要往状态和选择上思考,才能对框架产生自己的理解。
最优子结构性质是动态规划问题的必要条件,因此一般都是要你求最值的,直接从base case往后推导,以小博大。动态规划就是递推填表格(DP数组)的游戏,将问题转化。