面试官:你有m个鸡蛋,如何用起码的次数测出鸡蛋会在哪一层碎?

面试官:你有m个鸡蛋,如何用起码的次数测出鸡蛋会在哪一层碎?

假定你眼前有一栋n层的大楼和m个鸡蛋,假定将鸡蛋从f层或更高的处所放扔下去,鸡蛋才会碎,不然就不会。你需要设想一种战略来一定f的值,求最坏状况下扔鸡蛋次数的最小值。

leetcode原题链接

乍一看这道题很笼统,可以有的人一看到这个题目从来没做过,就懵逼了。实在不必慌张,再花狸狐哨的题目,末了都可以笼统成我们熟习的数据构造和算法去处理。

不限鸡蛋

起首,我们从一个简朴的版本最先明白,假如不限定鸡蛋个数,即把题目改成n层大楼和无穷个鸡蛋。那末这题要怎样解呢?
第一步就是要充足明白题意,消除题目中的滋扰,竖立模子:

  • 在一栋n层的大楼中寻觅目的楼层f –> 实在就是在一个1~n的数组中查找一个目的数字。
  • 鸡蛋碎了就代表楼层太高,不然就代表楼层太低 –> 每次尝试都能晓得当前数字是大了照样小了。

很显然,这就是一个二分查找能处理的题目。
扔鸡蛋的次数就是二分查找的比较次数,即log2(n+1)。

限定鸡蛋个数

那我们如今再来看限定鸡蛋个数状况下,一定没法用二分查找,然则由于求解的是一个最优值,我们自然而然地想到了动态计划。

四步走

动态计划的题目,这边供应一个思绪,就是四步走

  1. 题目建模,优化的目的函数是什么?束缚条件是什么?
  2. 划份子题目(状况)
  3. 列出状况转移方程及初值
  4. 是不是满足最优子构造性子

建模

这一步异常异常重要,它竖立在优越地明白题意的基础上。实在许多动态计划的题目都有如许的特征:

  1. 目的是求一个最优值
  2. 每一步决议计划有价值,总价值有一个束缚值。

而这道题:

  1. 目的函数f(n):代表在1~n的楼层中找到f层的尝试次数,我们的目的就是求出f(n)的最优值。
  2. 每一步决议计划的价值:鸡蛋可以会碎;总价值的束缚值:鸡蛋总个数。

划份子题目

我们晓得动态计划就是多阶段决议计划的历程,末了求解组合最优值。
我们先举一个简朴例子,来明白划份子题目的思绪,看下面这张图:

题目:求出发点集 S1~S5到尽头集 T1~T5的最短途径。

剖析这道题:定义子题目dis[i]代表节点i到尽头的最短间隔,没有束缚条件。
然后题目离别为4个阶段:

  1. 阶段1求出离尽头近来的C1~C4节点到尽头的最短途径dis[C1]~dis[C4]
  2. 阶段2求出离尽头近来的B2~B5节点到尽头的最短途径dis[B1]~dis[B5],需要竖立在阶段1的效果上盘算。比方B2节点到尽头有两条路,B2~C1,B2~C2,dis[C1]=2,B2到C1的长度=3;而dis[C2]=3,B2到C2的长度=6,因而dis[B2]=3+dis[B1]=5
  3. 阶段3和阶段4也是以此类推,终究就求出获得dis[S1]~dis[S5],得出最小途径为图中赤色的两条。

在这道题中,dis[i]就是离别出来的子题目,每一步决议计划都是一个子题目,而且每一个子题目都依赖于之前子题目的盘算效果。

因而,在动态计划中,定义一个合理的子题目异常重要

而扔鸡蛋这道题比上面这道题多了个束缚条件,我们把子题目定义为:用i个鸡蛋,在j层楼上扔,在最坏状况下一定目的楼层E的起码次数,记为状况f[i,j]

列出状况转移方程和初值

假如决议计划是在第k层扔下鸡蛋,有两种效果:

  1. 鸡蛋碎了,此时e<k,我们只能用i-1个蛋鄙人面的j-1层继承寻觅e。而且请求最坏状况下的次数起码,这是一个子题目,答案为f[i-1,j-1],总次数就是f[i-1,j-1]+1
  2. 鸡蛋没碎,此时e>=k,我们继承用这i个蛋在上面的j-k层寻觅E。注重:在k~j层寻觅和在1~(j-k)层寻觅没有区分,由于步骤都是一样的,只不过这(j-k)层在上面罢了,所以就把它看成是对1~(j-k)层的操纵。因而答案为f[i,j-k],次数为f[i,j-k]+1

初值:
当层数为0时,f[i,0]=0,当鸡蛋个数为1时,只能从下往上一层层扔,f[1,j]=j

由于是要最坏状况,所以这两种状况要取大值:max{f[i-1,j-1],f[i,j-k]},又要在一切决议计划中取最小值,所以动态转移方程是:

f(i,j)=min{max{f(i-1,k-1),f(i,j-k)}+1|1<=k<=j}

是不是满足最优子构造

获得了状况转移方程后,还需要推断我们的思绪是不是是准确。能用动态计划处理的题目必需要满足一个特征,叫做最优子构造特征

一个最优决议计划序列的任何子序列自身一定是相关于子序列的初始和完毕状况的最优决议计划序列。

这句话是什么意义呢?举个例子:f[4,5]示意4个鸡蛋、5层楼时的最优解,那它的子题目f[3,4],获得的解在3个鸡蛋、4层楼时也是最优解,它一切的子题目都满足这个特征。那这就满足了最优子构造特征。

一个反例

求 途径长度模10 效果最小的途径

照样像上面那道题一样,分红四个阶段。
依据动态计划的解法,阶段一CT,上面的路2 % 10 = 2,下面的路5 % 10 = 5,挑选上面那条,阶段二BC也挑选上面那条,以此类推,末了得出的效果途径是蓝色的这条。

但实际上,真正最优的是赤色的这条途径20 % 10 = 0。这就是由于不符合最优子构造,关于赤色途径的子构造CT阶段,最优解并非下面这条边。

时刻复杂度

递归树

假定m=3,n=4,我们来看一下f[3,4]的递归树。

图中色彩雷同的就是一样的状况,可以看出,反复的递归盘算许多,因而我们开设一个数组result[i,j]用于寄存f[i,j]的盘算构造,防止反复盘算,用空间换时刻。

代码

class Solution {
    private int[][] result;
    
    public int superEggDrop(int K, int N) {
        result = new int[K + 1][N + 1];

        for (int i = 1; i < K + 1; i++) {
            for (int j = 1; j < N + 1; j++) {
                result[i][j] = -1;
            }
        }

        return dp(K, N);
    }
    

    /**
     * @param i 盈余鸡蛋个数
     * @param j 楼层高度
     * @return
     */
   private int dp(int i, int j) {
        if (result[i][j] != -1) {
            return result[i][j];
        }
        if (i == 1) {
            return j;
        }
        if (j <= 1) {
            return j;
        }

        int min = Integer.MAX_VALUE;
        for (int k = 1; k <= j; k++) {
            int left = dp(i - 1, k - 1);
            result[i - 1][k - 1] = left;

            int right = dp(i, j - k);
            result[i][j - k] = right;

            int res = Math.max(left, right) + 1;
            if (res < min) {
                min = res;
            }
        }
        return min;
    }
    
   private static int log(int x) {
        double r = (Math.log(x) / Math.log(2));
        if ((r == Math.floor(r)) && !Double.isInfinite(r)) {
            return (int) r;
        } else {
            return (int) r + 1;
        }
    }
}

时刻复杂度

动态计划求时刻复杂度的要领是:

时刻复杂度 = 状况总数 * 状况转移方程的时刻复杂度

在这道题中,状况总个数很明显是m*n,而每一个状况f[i,j]的时刻复杂度为$O(j)$,$1 \leq j \leq n$,总时刻复杂度为$O(mn^2)$。

优化

$O(mn^2)$的时刻复杂度照样太高了。能不能想办法优化一下?

优化1

决议计划树

起首我们晓得,在一个1~n的数组中,查找目的数字,起码需要比较log2n次,也就是二分查找。这个理论可以经由过程决议计划树来证实:
我们运用二叉树来示意一切的决议计划,内部节点示意一次扔鸡蛋的决议计划,左子树示意碎了,右子树示意没碎,叶子节点代表E的一切效果。每一条从根节点到叶子节点的途径对应算法求出E之前的一切决议计划

内部节点(i,j),i示意鸡蛋个数,j示意在j层楼扔下。

当楼层高度n=5时,E总共有6种状况(n=0代表没找到),所以叶子节点的个数是n+1个。
而我们体贴的是树的高度,即决议计划的次数。依据二叉树理论:当树有n个叶子节点,数的高度最少为log2n,即比较次数在最坏状况下最少需要log2n次,也就是当这颗树只管均衡的时刻。

换句话说,在给定楼层n的状况下,决议计划次数的下限是log2(n+1),这个下限可以经由过程二分查找到达,只需鸡蛋的数目充足(就是我们适才议论的不限鸡蛋的状况)。

因而,一旦状况f[i,j]的鸡蛋个数i>log2(j+1),就不必盘算了,直接输出二分查找的比较次数log2(j+1)即可。

如许我们的状况总数就降为n*log2(k+1),时刻复杂度降为O(n^2 log2n)。

代码

/**
 * @param i 盈余鸡蛋个数
 * @param j 楼层高度
 * @return
 */
private int dp(int i, int j) {
    if (result[i][j] != -1) {
        return result[i][j];
    }
    if (i == 1) {
        return j;
    }
    if (j <= 1) {
        return j;
    }
    
    //此处剪枝优化
    int lowest = log(j + 1);
    if (i > lowest) {
        return lowest;
    }

    int min = Integer.MAX_VALUE;
    for (int k = 1; k <= j; k++) {
        int left = dp(i - 1, k - 1);
        result[i - 1][k - 1] = left;

        int right = dp(i, j - k);
        result[i][j - k] = right;

        int res = Math.max(left, right) + 1;
        if (res < min) {
            min = res;
        }
    }
    return min;
}

优化2

优化还未完毕,我们尝试从动态转移方程的函数性子入手,视察函数f(i,j),如下图:

我们可以发明一个规律,f(i,j)是依据j递增的单调函数,即f(i,j)>=f(i,j-1),这个性子是可以用数学归纳法证实的,在这里不做证实,有兴致的检察文末参考文献。

再来看动态转移方程:

f(i,j)=min{max{f(i-1,k-1),f(i,j-k)}+1|1<=k<=j}

由于$f(i,j)$具有单调性,因而$f(i-1,k-1)$是依据k递增的函数,$f(i,j-k)$是依据k递减的函数。

离别画出这两个函数的图象:

图象1:$f(i-1,k-1)$
图象2:$f(i,j-k)$
图象3:$max{f(i-1,k-1),f(i,j-k)}+1$,当k=kbest时,f到达最小值,我们的目的就是找到kbest的值

关于这个函数,可以运用二分查找来找到kbest:
假如f(i-1,k-1)<f(i,j-k),则k<kbest,即k在图中kbest的左侧;
假如f(i-1,k-1)>f(i,j-k),则k>kbest,即k在图中kbest的右侧。

代码

class EggDrop {
    private int[][] result;
    
    public int superEggDrop(int K, int N) {
        result = new int[K + 1][N + 1];

        for (int i = 1; i < K + 1; i++) {
            for (int j = 1; j < N + 1; j++) {
                result[i][j] = -1;
            }
        }

        return dp(K, N);
    }
    

    /**
     * @param i 盈余鸡蛋个数
     * @param j 楼层高度
     * @return
     */
   private int dp(int i, int j) {
        if (result[i][j] != -1) {
            return result[i][j];
        }
        if (i == 1) {
            return j;
        }
        if (j <= 1) {
            return j;
        }
        int lowest = log(j + 1);
        if (i >= lowest) {
            result[i][j] = lowest;
            return lowest;
        }

        int left = 1, right = j;
        while (left <= right) {
            int k = (left + right) / 2;
            int broken = dp(i - 1, k - 1);
            result[i - 1][k - 1] = broken;
            int notBroken = dp(i, j - k);
            result[i][j - k] = notBroken;

            if (broken < notBroken) {
                left = k + 1;
            } else if (broken > notBroken) {
                right = k - 1;
            } else {
                return notBroken + 1;
            }
        }
        //没找到,最小值就在left或许right中
        return Math.min(Math.max(dp(i - 1, left - 1), dp(i, j - left)),
            Math.max(dp(i - 1, right - 1), dp(i, j - right))) + 1;
    }
    
   private static int log(int x) {
        double r = (Math.log(x) / Math.log(2));
        if ((r == Math.floor(r)) && !Double.isInfinite(r)) {
            return (int) r;
        } else {
            return (int) r + 1;
        }
    }
}

时刻复杂度

如今状况转移方程的时刻复杂度降为了O(log2N),算法的时刻复杂度降为O(Nlog2^2 N)。

优化3

如今无论是状况总数照样状况转移方程都很难优化了,但另有一种算法有更低的时刻复杂度。
我们定义一个新的状况g(i,j),它示意用j个蛋尝试i次在最坏状况下能一定E的最高楼层数

动态转移方程

假定在k层扔下一只鸡蛋:

假如碎了,则在背面的(i-1)次里,我们要用(j-1)个蛋鄙人面的楼层中一定E。为了使 g(i,j)到达最大,我们固然愿望下面的楼层数到达最多,这是一个子题目,答案为 g(i-1,j-1)。

假如没碎,则在背面(i-1)次里,我们要用j个蛋在上面的楼层中一定E,这一样需要楼层数到达最多,便为g(i-1,j) 。

因而动态转移方程为:

g(i,j)=g(i-1,j-1)+g(i-1,j)+1

边境值

当i=1时,示意只尝试一次,那最多只能一定一层楼,即g(1,j)=1 (j>=1)

当j=1是,示意只要一个蛋,那只能第一层一层层往上扔,最坏状况下一向扔到顶层,即g(i,1)=i (i>=1)

然后我们的目的就是找到一个尝试次数x,使x满足g(x-1,m)<ng(x,m)>=n

代码

public class EggDrop {

    private int dp(int iTime, int j) {
        if (iTime == 1) {
            return 1;
        }
        if (j == 1) {
            return iTime;
        }
        return dp(iTime - 1, j - 1) + dp(iTime - 1, j) + 1;
    }

    public int superEggDrop(int i, int j) {
        int ans = 1;
        while (dp(ans, i) < j) {
            ans++;
        }
        return ans;
    }
}

这个算法的时刻复杂度是$O(\sqrt{N})$,证实比较复杂,这里就不展开了,可以参考文末文献。

小结

末了我们总结一下动态计划算法的解题要领:

  • 四步走:题目建模、定义子题目、动态转移方程、最优子构造。
  • 时刻复杂度 = 状况总数 * 状况转移方程的时刻复杂度。
  • 斟酌是不是需要设置标记,比方有的题目还请求打印出最小途径。
  • 写代码,递归和轮回挑选你熟习的来写。
  • 假如时刻复杂度不能接收,斟酌能不能优化算法。

优化思绪

  • 是不是可以剪枝优化(优化1)
  • 从函数自身的数学性子入手(优化2)
  • 转换思绪,尝试一下别的状况转移方程(优化3)
  • ……

动态计划在算法中属于较难的题型,难点就在定义子题目和写出动态转移方程。所以需要勤加练习,练习本身的头脑。
这里给出几道动态计划的典范题目,这几道题都需要吃透,可以用本文中提到的四步走的体式格局来思索和解题。

Maximum Length of Repeated Subarray
Coin Change
Partition Equal Subset Sum

末了:

参考文献

国度集训队朱晨曦论文
知乎-如何用起码的次数测出鸡蛋会在哪一层摔碎?

Up Next:

ABP vNext 不使用工作单位为何会抛出非常

ABP vNext 不使用工作单位为何会抛出非常