leetcode-887. 鸡蛋掉落

思路：动态规划

定义数组含义：dp(K,N)表示有K个鸡蛋，N层楼，在最坏的情况下，最小的移动次数

边界条件：只有一个鸡蛋，N次，有0层，返回0

选择：遍历从1到N层楼，选择

res=min(res,max(dp(K-1,i-1),dp(K,N-i)));

返回res

优化：

分析：dp(K-1,i-1)是随着递增的函数，dp(K,N-i)是随着i递减的函数，

找min(max(dp(K-1,i),dp(N,N-i)))；

方法：使用二分法找中间那个点，有可能是在left和right中间，有可能是等于left和right。结果定位到left和right两个点，再比较两个点的max(dp(K-1,left-1),dp(K,N-left))、max(dp(K-1,right-1),dp(K,N-right))哪一个值最小取哪一个

class Solution {
public:
    unordered_map<int,int> memo;
    int dp(int K,int N){
    if(memo.find(N*100+K)==memo.end()){
        int ans=0;
        if(N==0) ans=0;
        else if(K==1) ans=N;
        else {
            int left=1;
            int right=N;
            while(left+1<right){
                int mid=(right+left)/2;
                int t1=dp(K-1,mid-1);
                int t2=dp(K,N-mid);
                if(t1<t2) left=mid;
                else if(t1>t2) right=mid;
                else left=right=mid;
            }
            ans=1+min(max(dp(K-1,left-1),dp(K,N-left)),max(dp(K-1,right-1),dp(K,N-right)));
        }
        memo[N*100+K]=ans;
    }
    return memo[N*100+K];
    }
    int superEggDrop(int K, int N) {
       return dp(K,N);
    }
};
           

#include <iostream>
#include<math.h>
#include<unordered_map>
using namespace std;
unordered_map<int,int> memo;
int min1(int a,int b){
return a<b?b:a;}
int dp(int K,int N)
{
    if(memo.find(N*10000+K)==memo.end())
    {
        int ans=0;
        if(N==0) ans=0;
        else if(K==1) ans=N;
        else
        {
            int left=1;
            int right=N;
            while(left+1<right)
            {
                int mid=left+(right-left)/2;
                int t1=dp(K-1,mid-1);
                int t2=dp(K,N-mid);
                if(t1<t2)  left=mid;
                else if(t1>t2) right=mid;
                else left=right=mid;
            }
            ans=1+min(max(dp(K-1,left-1),dp(K,N-left)),max(dp(K-1,right-1),dp(K,N-right)));
        }
        memo[N*10000+K]=ans;
    }
    return memo[N*10000+K];

}


int main()
{

    int K=4;
    int N=500;
    cout<<dp(K,N);
}