本文主要是介绍高楼扔鸡蛋-memorization search，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
title: 高楼扔鸡蛋-memorization search
date: 2020-06-07 21:51:12
tags:
高楼扔鸡蛋-memorization search
题解:
LeetCode 887. Super Egg Drop.
这是一道经典的谷歌面试题，某公司今天的笔试题出了这道题（只不过扔的不是鸡蛋）。
理解题意
这道题是总共有N层楼，K个鸡蛋，找到鸡蛋摔破的极限楼层。最小需要尝试多少次，
(表示我第一次看到这道题，以为是一道数学题，并且还想眼巴巴的算出来。)
考虑状态转移，很容易想到动态规划。
假设从h楼摔下，如果摔碎，则状态变为：（K-1, h-1) （即K-1个鸡蛋，总共有h-1楼）
如果没摔碎，则状态变为：（K, N-h)
由此很容易写出递推式：
d p [ k ] [ n ] = m i n ( 1 + m a x ( d p [ k − 1 ] [ i − 1 ] , d p [ k ] [ n − i ] ) ) i = 1... n dp[k][n] = min(1+max(dp[k-1][i-1], dp[k][n-i])) \ i=1...n dp[k][n]=min(1+max(dp[k−1][i−1],dp[k][n−i])) i=1...n
由递推式得到代码：
class Solution {public int superEggDrop(int K, int N) {int[][] dp = new int[K+1][N这篇关于高楼扔鸡蛋-memorization search的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
