一道经典题

面试的过程也是补全自己的过程,要正视自己的缺点,补足落下的知识,虚心求教,终身学习。

来源:百度面试,Google面试题

题目

有一栋100层高楼,从某一层开始扔下的苹果刚好摔坏,现有两个苹果,试用最简便的方法确定这个恰好摔坏苹果的那层。

一幢 100 层的大楼,给你两个鹰蛋。如果在第 n 层扔下鹰蛋,鹰蛋不碎,那么从第 n-1 层扔鹰蛋,都不碎。这两只鹰蛋一模一样,不碎的话可以扔无数次。最高从哪层楼扔下时鹰蛋不会碎?

  1. 如果有无数个鹰蛋,如何求解?
  2. 如果只有两个鹰蛋,如何求解?

不成熟的思考

我给出的解答是进行分段,第一个球每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. 如果鹰蛋只剩1个,那么只能对所有的楼层进行穷举;
  2. 如果楼层是0,那么试探0次;
  3. 如果楼层是1,那么试探1次。

楼层示意

状态转移方程:F(m,n) = MIN{MAX{F(i-1,n-1)+1, F(m-i,n)+1}}};(0<i<m)

动态规划

labuladong的算法小抄

程序员小灰-动态规划

定义

动态规划(Dynamic Programming,简称DP)是运筹学的一个分支,它是解决多阶段决策过程最优化的一种数学方法。把多阶段问题变换为一系列相互联系的的单阶段问题,然后逐个加以解决

这里提到动态规划其实是一种数学方法,是求解某类问题的一种方法,而不是一种特殊的算法,没有一个标准的数学表达式或明确定义的一种规则。

总结起来就是一句话:大事化小,小事化了。

具体来说,动态规划的流程为:暴力的递归解法 -> 带备忘录的递归解法 -> 迭代的动态规划解法。

就思考流程来说:找到状态和选择 -> 明确dp数组/函数的定义 -> 寻找状态之间的关系。

递归方法

1. 问题建模

每一个步骤中,进行分状态定义,再利用递归简化。动态规划当中包含三个重要的概念:最优子结构边界状态转移公式

2. 求解问题

拿一个递归方法举例:

// 求解n=8时,Fun返回值
public int Fun(int n)
{
if(n==0) return 1;
if(n<0) return -1;
return Fun(n-3)+Fun(n-2);
}

用递归的思路直接做,这是一颗二叉树,树的节点个数就是递归方法需要计算的次数(图中最后一步省略了)。这棵二叉树高度是n-1节点个数接近·2^(n-1),时间复杂度近似看成O(2^n)。

运算二叉树

备忘录算法

可以看到上方的递归图有些相同的参数被重复计算了,例如中间的两个Fun(3),这样越往下走,重复的越多。优化方式可以用缓存,创建一个哈希表,每次将不同参数结果存入,遇到相同参数时,从哈希表中取出即可。这个方法叫做备忘录算法。 +

// 求解num=8时,Fun返回值
public int Fun(int n, Dictionary<int,int> map)
{
if(n==0) return 1;
if(n<0) return -1;
if(map.ContainsKey(n))
{
return map[n];
}else
{
int value = Fun(n-3,map)+Fun(n-2,map);
map.Add(n,value);
return value;
}
}

集合map是一个备忘录,每次需要计算F(n)的时候,会首先从map中寻找匹配元素,如果存在就直接返回结果,不存在就计算结果,存入备忘录中。时间复杂度和空间复杂度都是O(n)。

动态规划

上面那个备忘录算法当然不是真正的动态规划实现,可以进一步减小空间复杂度。思路逆转,不对F(n)自顶向下做递归,而是自底向上用迭代。每一次迭代过程中,只要保留之前的两个状态,就可以推导出新的状态。

public int Fun(int n)
{
// 感谢电压酱
int[] dp = new int[n + 3 + 1];
dp[0] = dp[1] = dp[2] = -1;
dp[3] = 1;
for(int i = 4; i < n + 3 + 1; i++)
{
dp[i] = dp[i - 3] + dp[i - 2];
}
return dp[n + 3];
}

练习

动态规划解题套路框架

LeetCode:509.斐波那契数322.零钱兑换

动态规划问题的一般形式就是求最值,例如求最长递增子序列,最小编辑距离等。

求动态规划的核心问题是穷举。这类问题存在重叠子问题,具备最优子结构,需要正确的状态转移方程。一般来说,写出状态转移方程是最困难的。

思考框架:明确base case,明确状态,明确选择,定义dp数组/函数的含义。

代码框架:

# 初始化 base case
dp[0][0][...] = base
# 进行状态转移
for 状态1 in 状态1的所有取值:
for 状态2 in 状态2的所有取值:
for ...
dp[状态1][状态2][...] = 求最值(选择1, 选择2 ...)

斐波那契数列

斐波那契数,通常用 F(n) 表示,形成的序列称为斐波那契数列。该数列由 01 开始,后面的每一项数字都是前面两项数字的和。也就是:

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)
{
if(N<1) return 0;
if(N==1 || N==2) return 1;
return fib(N - 1) + fib(N - 2);
}

根据上方的递归方法,可以画出递归树,能够看出比较低效。时间复杂度为:子问题的个数 乘以 解决一个子问题需要的时间。子问题个数是递归树中节点的总数O(2^n),解决子问题的时间是加法O(1),总时间为两者相乘O(2^n)。可以看到递归树中有大量重复的计算,这就是动态规划问题的第一个性质:重叠子问题

带备忘录的递归

根据上方的备忘录算法,添加一个哈希表,直接将答案拿来用(空间换时间)。

int fib(int N)
{
if(N <= 1) return N;
Dictionary<int,int> map = new Dictionary<int,int>();
map.Add(0,0);
map.Add(1,1);
return fib(N,map);
}
int fib(int N,Dictionary<int,int> map)
{
if(map.ContainsKey(N)) return map[N];
int value = Fib(N-1, map) + Fib(N-2, map);
map.Add(N,value);
return value;
}

带备忘录的递归算法,把一颗存在巨量冗余的递归树“减枝”,极大减少了子问题的个数。时间复杂度是O(n)。这种方法叫做自顶向下,而动态规划叫自底向上

自顶向下是像我们画递归树一样,从要求的大问题向下分解为小问题。而自底向上是从小问题开始往上推,直到推到我们想要的答案。这也就是动态规划一般脱离递归,而由循环迭代完成的原因。

dp数组的迭代解法

我们把这个备忘录独立出来成为一张表,叫做DP table,在这张表上完成自底向上即可。

int fib(int N)
{
int[] dp = new int[N+1];
if(N>0) dp[1]=1;
if(N>1) dp[2]=1;
for(int i = 3; i <= N; i++)
{
dp[i] = dp[i-1] + dp[i-2];
}
return dp[N];
}

dp数组

实际上就是反过来算剪枝的结果。

状态转移方程

实际上是描述问题结构的数学形式:

斐波那契

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)
{
if(n == 0) return 0;
if(n == 2 || n == 1) return 1;
int prev = 1;
int curr = 1;
for(int i = 3; i <=n; i ++)
{
int sum = prev + curr;
prev = curr;
curr = sum;
}
return curr;
}

凑零钱问题

题目:给出k种面值的硬币,面值分别为c1,c2...ck,每种硬币的数量无限,再给一个总金额amount,问最少需要几枚硬币凑出这个金额,如果不可能凑出,返回-1。方法声明如下:

// coins中是可选硬币面值,amount是目标金额
int coinChange(int[] coins, int amount);

例:当k = 3,面值为1,2,5,总金额amount = 11。那么最少需要3枚硬币凑出,即11=5+5+1。

计算机如何解决这个问题?把所有可能的凑硬币方法琼剧出来,然后找找看最少需要多少枚硬币。

暴力递归

这个问题是动态规划问题,因为具有最优子结构,即子问题间相互独立:如果想求amount = 11的最少硬币数,只要求出amount = 10的数量,再加1即可(添加一枚面值1的硬币)。因为硬币数量是没有限制的,所以子问题之间没有限制,是相互独立的。

如何列出正确的状态转移方程?

  1. 确定base case:目标金额amount = 0时算法返回0;
  2. 确定状态,也就是原问题和子问题中会变化的变量。由于硬币数量无限,硬币面额也是给定的,只有目标金额会不断向base case靠近,因此唯一的状态就是目标金额amount
  3. 确定选择,也就是导致状态产生变化的行为。目标金额变化的原因是在选择硬币,每选择一枚硬币,就相当于减少了目标金额。选择硬币的面额,就是选择。
  4. 明确dp函数/数组的定义。暴力递归是自顶向下的解法,所以会有递归的dp函数,一般来说函数的参数就是状态转移中会变化的量,也就是状态;函数的返回值就是我们要计算的量。因此我们可以这样定义:

dp(n)的定义:输入一个目标金额n,返回凑出目标金额n的最少硬币数量。

def coinChange(coins: List[int], amount: int):
def dp(n):
# base case
if n == 0: return 0
if n < 0: return -1
# 求最小值,所以初始化为正无穷
res = float('INF')
for coin in coins:
subproblem = dp(n - coin)
# 子问题无解,跳过
if subproblem == -1: continue
res = min(res, 1 + subproblem)
return res if res != float('INF') else -1
return dp(amount)

数学形式的状态转移方程:

凑零钱

至此暴力法解决,时间复杂度为O(k*n^k),指数级别。

public class Solution {
public int CoinChange(int[] coins, int amount)
{
return dp(coins,amount);
}
public int dp(int[] coins, int amount)
{
if(amount == 0) return 0;
if(amount < 0) return -1;
int res = int.MaxValue;
for(int i = 0; i < coins.Length; i++)
{
int sub = dp(coins, amount - coins[i]);
if(sub == -1) continue;
res = Math.Min(res, 1 + sub);
}
if(res != int.MaxValue) return res;
else return -1;
}
}// 超时

带备忘录递归

public class Solution {
public int CoinChange(int[] coins, int amount)
{
Dictionary<int,int> memo = new Dictionary<int,int>();
return dp(coins,amount,memo);
}
public int dp(int[] coins, int amount, Dictionary<int,int> memo)
{
if(memo.ContainsKey(amount)) return memo[amount];
if(amount == 0) return 0;
if(amount < 0) return -1;
int res = int.MaxValue;
for(int i = 0; i < coins.Length; i++)
{
int sub = dp(coins, amount - coins[i],memo);
if(sub == -1) continue;
res = Math.Min(res, 1 + sub);
}
memo[amount] = res != int.MaxValue?res:-1;
return memo[amount];
}
}

还是很慢,时间复杂度O(kn)。

dp数组的迭代解法

主要问题是确定dp数组的定义:当目标金额为i时,至少需要dp[i]枚硬币凑出。

根据开头的动态规划代码框架可以写出:

public class Solution {
public int CoinChange(int[] coins, int amount)
{
int[] dp = new int[amount + 1];
//base case
for(int i = 0; i < amount + 1; i ++)
{
dp[i] = amount + 1;
}
dp[0] = 0;
// for循环遍历所有状态
for(int i = 0; i < dp.Length; i++)
{
for(int j = 0; j < coins.Length; j++)
{
if(i - coins[j] < 0) continue;
dp[i] = Math.Min(dp[i], 1+ dp[i - coins[j]]);
}
}
return (dp[amount] != amount + 1)? dp[amount]:-1;
}
}

dp数组定义

dp初始化成amount+1的原因是,凑成amount金额的硬币数最多只可能等于amount(也就是全用1元),所以初始化为amount+1相当于正无穷,可以取最小值。

总结

计算机解决问题的办法就是穷举,算法设计是先思考“如何穷举”,再追求“如何聪明地穷举”。列出状态转移方程就是解决“如何穷举”,备忘录、DP table就是在追求“如何聪明地穷举”。无非是空间换时间。

阅读题目时,要往状态选择上思考,才能对框架产生自己的理解。

最优子结构性质是动态规划问题的必要条件,因此一般都是要你求最值的,直接从base case往后推导,以小博大。动态规划就是递推填表格(DP数组)的游戏,将问题转化。