设n为石墩数,m为荷叶数 ,设F[n,m]表示当有n个石墩,m个荷叶时,能跳过去的最多青蛙数，我们现在可以增加一个石墩，此时就有n+1个石墩了,把第n+1个石墩看成右岸,这样就可以把F[n,m]个青蛙从左岸跳到第n+1个石墩上(借助原来河里的n个石墩,m个荷叶), 这时第n+1个石墩上就有F[n,m]个青蛙了，此时河里还有n个空石墩,m个空荷叶,还可以帮助F[n,m]个青蛙从左岸跳到真正的右岸,此时再把第n+1个石墩看成左岸, 借助河里的n个石墩,m个荷叶,顺利的跳到右岸青蛙的身上.至此一共可以跳过去 2*F[n,m]个青蛙.
由此可知： 关系式 F[n+1，m]=2*F[n，m]
推导: F[n，m]=2*F[n-1，m]
=4*F[n-2，m]
……
=(2^i)*F[n-i，m]
……
=(2^n)*F[0，m]
当n=0时,河里只有m个荷叶,每个叶上只能有一个青蛙,再加上从右岸可以直接跳到左岸的一只,所以共有m+1个青蛙,即F[0,m]=m+1;所以
F[n，m]=(m+1）*2^n
免责声明：本平台仅供信息发布交流之途，请谨慎判断信息真伪。如遇虚假诈骗信息，请立即举报
举报