Update 高楼扔鸡蛋问题.md

tianzhongwei · labuladong · commit a2e0bafb3bc0 · 2020-06-24T12:58:25.000+08:00
将添加的C++代码移动到了文末
diff --git a/动态规划系列/高楼扔鸡蛋问题.md b/动态规划系列/高楼扔鸡蛋问题.md
@@ -230,8 +230,43 @@ def superEggDrop(self, K: int, N: int) -> int:
 
 ![labuladong](../pictures/labuladong.png)
 
+[renxiaoyao](https://github.com/tianzhongwei) 提供C++解法代码：
+1) 状态定义一：动态规划 + 二分查找
+```C++
+class Solution {
+public:
+    int superEggDrop(int K,int N) {
+        vector<vector<int>> dp(N + 1,vector<int>(K + 1,0));
+        for(int j = 1 ; j <= K ; ++j)
+            dp[1][j] = 1;
+        
+        for(int i = 1 ; i <= N ; ++i)
+            dp[i][1] = i;
+        for(int i = 2 ; i <= N ; ++i)
+            for(int j = 2 ; j <= K ; ++j)
+                dp[i][j] = binary_Valley(i,j,dp);
+        return dp[N][K];
+    }
+private:
+    int binary_Valley(int floors,int eggs,vector<vector<int>>& dp) {
+        int l = 1;
+        int r = floors;
+        while(l < r) {
+            int LMid = l + (r - l) / 2;
+            int broken = dp[LMid - 1][eggs - 1];
+            int not_broken = dp[floors - LMid][eggs];
+            if(not_broken > broken)
+                l = LMid + 1;
+            else
+                r = LMid;
+        }
+        return max(dp[r - 1][eggs - 1],dp[floors - r][eggs]) + 1;
+    }
+};
+```
+
 [上一篇：编辑距离](../动态规划系列/编辑距离.md)
 
 [下一篇：经典动态规划问题：高楼扔鸡蛋（进阶）](../动态规划系列/高楼扔鸡蛋进阶.md)
 
-[目录](../README.md#目录)
+[目录](../README.md#目录)
