一道经典题

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

来源：百度面试，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) = 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) 表示，形成的序列称为斐波那契数列。该数列由 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)
{
    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的硬币）。因为硬币数量是没有限制的，所以子问题之间没有限制，是相互独立的。

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

确定base case：目标金额amount = 0时算法返回0；
确定状态，也就是原问题和子问题中会变化的变量。由于硬币数量无限，硬币面额也是给定的，只有目标金额会不断向base case靠近，因此唯一的状态就是目标金额amount。
确定选择，也就是导致状态产生变化的行为。目标金额变化的原因是在选择硬币，每选择一枚硬币，就相当于减少了目标金额。选择硬币的面额，就是选择。
明确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;
    }
}