现在是疫情期间,被动裁员,呆在宿舍没事儿做,在YouTube上看见了李永乐老师的一个双蛋问题的视频,就是众所周知的动态规划问题,然后就做了一下。 1,问题描述: 有t层楼,n个鸡蛋,鸡蛋是相同的,临界楼层是指从某个楼层之上抛下来,都会碎,但从这个楼层之下抛下来,都不会碎。没有碎的鸡蛋可以重复使用。试假设能找到这个临界楼层需要抛投的最少次数。 2,问题分析,画表格。 假设横轴为鸡蛋数,纵轴为楼层数,值为最少抛投次数。填表格。 这里要求的是能找到临界值至少抛投的次数。一看就是动态规划,直接找递归式。 设M(t,n)为在从t层楼,n个蛋的情况下需要抛投的最少次数,情况有多少种呢。当然是t种,从每一