最初的想法应该是:d(i,j) 表示用 i 个球在高度为 j 的楼里做实验,需要的最少实验次数。
可是层数太大,无法作为状态。进行一下问题的转换:设 d(i,j) 表示用 i 个球做 j 次实验最高可以测试多少层楼。最后只需选取 d(k,j) >= n 的最小的 j 即可
状态的转移很有意思:
假设我们现在对 d(i,j) 做决策,如果气球爆了,则实验可以测定的层数等于 d(i-1, j-1) + 1。如果气球没爆,我们可以继续向上面的楼层搜索。向上最多能测定 d(i, j-1) 层。保证上下所有的楼层都能搜到,d(i,j) 最大值则是向下和向上搜索的层数的最大值的和,......
阅读全文