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);
}