动态规划（Dynamic programming, DP）是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 常常适用于具有 重叠子问题 和 最优子结构性质的问题，在编程中可以通过记忆化存储减少重复子问题的计算量。
经典问题#
掉蛋谜题(Egg dropping puzzle)#
一个著名的谜题是从建筑物上掉落鸡蛋，以确定鸡蛋从多高层开始破裂。
F(d) 表示：使用 2 个鸡蛋🥚、最多投掷 d 次时，最多可以判定（覆盖）的楼层数（即若楼层数不超过 F(d)，一定能在 d 次内找到临界楼层）。
考虑一次投掷，会有两种结果：
- 碎了：
- 没碎：
F(d) = F(d-1) + d
F(d) = 1 + 2 + 3 + … + d = d(d+1)/2
使其大于100，得最小整数d = 14.