思维训练：隐形的青蛙

由于此题已经不接受新题解所以我迫不得已又只能来讨论版了 : (

如题我粗略地看到题解区的大佬们似乎都是用偏数学的方法递推出了通项公式在这里我想给出一个偏思维训练的方式来找到答案我叫它 隐形的青蛙

让我们想想看对于以及有n个石墩m片荷叶（以后简称[n][m]）的局面下多上那么一片荷叶（[n][m+1]）会怎么样

如果我们想用上那片荷叶很好的尝试当然是第一步把那只最上面重量第一轻的青蛙（以后简称“1” 其他同理）

然后我们就会惊讶地发现由于“1”只能在最后跳上右岸的石墩 D 所以“1”在接下来的时间里就像隐形了一样只能等最后现出原形

而剩下的“2”到“N”就像在局面 [n][m] 下一样他们的数量自然是 dp[n][m]

于是 dp[n][m +1] = dp[n][m] + 1；

显然 dp[0][0]=1 故而 dp[0][m] = m+1；

那么如果[n][m]的局面下多上那么一个石墩（[n][m+1]）会怎么样

我们尝试让尽可能多的青蛙在那多的一个石墩上隐形

数量是多少？

我们惊讶地发现由于右岸的石墩 D 跳上去就不能反悔我们不能让要隐形的青蛙跳上去

于是隐形的青蛙的数量就等于dp[n][m]！！！

因为此时多的一个石墩已经天然拥有右岸的石墩 D 的所有特性！！！

细节解释可以不看：

如果一个青蛙想从这个石墩跳下去

要么此时“你”反悔了那么此时就不是这只青蛙跳上去的最佳时机它本就不应该跳上去

要么此时就是最佳时机那么这只青蛙跳下去后下一步就要跳回来

那么接下来有dp[n][m]只青蛙连带着它们所处的石墩一起隐形了

局面重返[n][m] 于是右岸的石墩 D 上的青蛙最多dp[n][m]只

之后隐形的青蛙因为不可能回到左岸的石墩 A

局面仍是[n][m] 那dp[n][m]只青蛙刚好可以全部跳上右岸的石墩 D

于是dp[n + 1][m] = 2 * dp[n][m]

大家可以试试推一下为什么隐形石墩又可以拥有左岸的石墩 A 的所有特性^_^

最后可知 dp[n][m]=（m + 1）* 2^n !!!

思维训练结束^_^

讨论操作