반복 사상 해결 leetcode 계란 드랍

제목

계란 K개를 얻을 수 있고 1부터 N까지 N층이 있는 건물을 사용할 수 있다.
모든 알의 기능은 똑같다. 만약 알이 깨진다면, 너는 다시는 그것을 떨어뜨릴 수 없다.
너는 층 F가 존재한다는 것을 알고 있다. 0<=F<=N을 만족시키면 F보다 높은 층에서 떨어진 계란은 모두 깨지고 F층이나 그보다 낮은 층에서 떨어진 계란은 깨지지 않는다.
이동할 때마다 계란 하나를 꺼내서 (온전한 계란이 있다면) 임의의 층에서 X를 던져 버릴 수 있다.
너의 목표는 F의 값이 얼마인지 정확히 아는 것이다.
F의 초기 값이 어떻든지 간에, 당신은 F의 값의 최소 이동 횟수가 얼마인지 확정합니까?
예 1:

 ：K = 1, N = 2
 ：2
 ：
  1  。 ，  F = 0 。
 ，  2  。 ，  F = 1 。
 ，  F = 2 。
 ，  2   F  。

예 2:

 ：K = 2, N = 6
 ：3

예 3:

 ：K = 3, N = 14
 ：4

팁:

1 <= K <= 100
1 <= N <= 10000

출처: 리코드(LeetCode) 링크:https://leetcode-cn.com/problems/super-egg-drop저작권은 인터넷 소유에 귀속된다.상업 전재는 정부에 연락하여 권한을 부여하고, 비상업 전재는 출처를 명시해 주십시오.

생각

어려운 문제이니 이영락 선생이 설명한 쌍알 문제를 기초적으로 이해하는 것을 추천한다.
사고방식으로 말하자면leetcode 공식 문제풀이 중의 세 번째 해법은 오히려 가장 이해하기 쉽기 때문에 본고는 내가 이해한 세 번째 방법을 설명하고자 한다.
이 문제는 N층에서 K개의 계란을 사용하고 적어도 M번을 던지면 임가층 F를 찾을 수 있다는 것을 알고 있다.또 K개의 계란으로 T번을 조작하면 가장 높은 층이 얼마인지 찾을 수 있다고 해석할 수 있다.최고층 만족 필요 >=N.그래서 f(T, K)>=N의 T값 귀속(동적 기획) 사고 과정에 대해 f(T, K)를 어떻게 구하는지 찾아내야 한다. 우리는 계란을 던져 도대체 무슨 일이 일어났는지 생각해 보자.
만약 계란이 깨지지 않았다면 대응하는 것은 f(T-1,K)이다. 즉, 이 층의 위쪽에 f(T-1,K)층이 있을 수 있다.
계란이 깨지면 f(T-1, K-1), 즉 이 층 아래에 f(T-1, K-1)층이 있을 수 있다.
따라서 우리는 상태 이동 방정식을 쓸 수 있다.

f(T, K) = 1 + f(T-1, K-1) + f(T-1, K)

경계 조건은 T≥1일 때 f(T,1)=T, K≥1일 때 f(1,K)=1이다.
그럼 T는 최대 몇 개까지 가능할까요?조작 횟수는 반드시 층수를 초과하지 않기 때문에 T≤N, 우리는 f(N, K) 내의 모든 f값을 계산하면 된다.

go code

기본 코드

func superEggDrop(K int, N int) int {
    if N==1 {
        return 1
    }
    var f [][]int
    for i:=0;i<=N;i++ {
        item := make([]int,K+1)
        f = append(f,item)
    }

    for i:=1;i<=K;i++ {
        f[1][i] = 1
    }
    ans := -1
    for i:=2;i<=N;i++ {
        for j:=1;j<=K;j++ {
            f[i][j] = 1+f[i-1][j-1]+f[i-1][j]
        }
        if f[i][K]>=N {
            ans = i
            break
        }
    }
    return ans
}

진급 최적화 코드

func superEggDrop(K int, N int) int {
    times := 1
	for {
	    if getTimes(times, K) >= N {
			break
		}
		times ++
	}
	return times
}


func getTimes(times, eggCount int) int {
	if times == 1 || eggCount == 1{
		return times
	}
	return getTimes(times - 1, eggCount - 1) + 1 + getTimes(times - 1, eggCount)
}

총결산

난제에 부딪혔을 때, 여전히 기초적인 사상으로 돌아가야 한다

예를 들어 본 문제에서 배운 기초 사상은 귀착이다