The title

  1. Egg drop

Topic describes

You get K eggs and you can use a building with N floors from 1 to N and each egg does the same thing. If one egg breaks, you can’t drop it. You know that there is floor F, where 0 <= F <= N and any egg that falls from floor F will break, and any egg that falls from floor F or below will not break. For each move, you can take an egg (if you have a whole egg) and drop it from any floor X (satisfying 1 <= X <= N). Your goal is to know exactly what the value of F is. Whatever the initial value of F is, what is the minimum number of moves you can make in the value of F?

case

The sample a

Enter K =1, N = 2Output:2Explanation: Eggs from1The building fell. If it breaks, we definitely know that F is equal to0. Otherwise, eggs from2The building fell. If it breaks, we definitely know that F is equal to1. If it didn't break, then we definitely know that F is equal to2. So, in the worst case we need to move2Times to figure out what F is.Copy the code

Example 2

Enter K =2, N = 6Output:3
Copy the code

Example 3

Enter K =3, N = 14Output:4
Copy the code

prompt

1 <= K <= 100
1 <= N <= 10000
Copy the code

Train of thought

Given: K eggs, N stories

What’s the state? It’s the amount of change, and we know that there are two of them, the number of eggs we currently have K, and the number of floors we need to test N, and as we test, the number of eggs goes down, the number of floors might go down, and that’s the change in state.

What are the options? Which floor to throw eggs at

State transfer if the I layer is selected to throw eggs if the eggs are broken K->K-1, 0~N ->0 ~ I-1 If the eggs are not broken K->K, 0~N -> I +1 ~N

code

package leetcode

import (
	"fmt"
)

// superEggDrop
// The egg falls
func superEggDrop(K int, N int) int {
	// The memo addresses overlapping subissues
	meno := map[string]int{}

	var dp func(K, N int) int
	dp = func(K, N int) int {
		// base case
		// The floor is 0
		if N == 0 {
			return 0
		}
		// There is only one egg
		if K == 1 {
			return N
		}

		// Check whether the memo exists
		key := fmt.Sprintf("%d%d", K, N)
		if rs, ok := meno[key]; ok {
			// log.Println(rs)
			return rs
		}

		res := 1<<31 - 1
		for i := 1; i <= N; i++ {
			// Worst case scenario
			K->K, 0~N -> I +1 ~N
			// The egg is broken: K->K-1, 0~N -> 0~ i-1
			maxNums := max(dp(K, N-i), dp(K- 1, i- 1)) + 1
			// Minimum number of eggs thrown
			res = min(res, maxNums)
		}
		meno[key] = res
		return res
	}
	return dp(K, N)
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a > b {
		return b
	}
	return a
}

// superEggDrop
// The egg falls
// Use dichotomy to improve efficiency
func superEggDropV2(K int, N int) int {
	// The memo addresses overlapping subissues
	meno := map[string]int{}

	var dp func(K, N int) int
	dp = func(K, N int) int {
		// base case
		// The floor is 0
		if N == 0 {
			return 0
		}
		// There is only one egg
		if K == 1 {
			return N
		}

		// Check whether the memo exists
		key := fmt.Sprintf("%d%d", K, N)
		if rs, ok := meno[key]; ok {
			return rs
		}

		res := 1<<31 - 1
		left, right := 1, N
		for left <= right {
			mid := (left + right) / 2
			/ / broken
			broken := dp(K- 1, mid- 1)
			/ / not broken
			notBroken := dp(K, N-mid)

			if broken > notBroken {
				right = mid - 1
				res = min(res, broken+1)}else {
				left = mid + 1
				res = min(res, notBroken+1)
			}
		}
		meno[key] = res
		return res
	}
	return dp(K, N)
}
Copy the code

reference

Source: LeetCode link: leetcode-cn.com/problems/su… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

[Algorithm cheat sheet @ Fu Dong Lai]