Ex10-II 青蛙跳台问题

题目描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

解题思路

用动态规划的思路来思考这个问题，有可能两种情况青蛙会到达第n级台阶：

• 第一种，从第n-1级台阶跳了1级台阶上来；
• 第二种，从第n-2级台阶跳了2级上来。

注意到，当n=1时，结果是1；当n=2时，结果是2。如果当n=0时，结果是1的话，这个问题也就是一个斐波那契数列的问题，类似于10-II。

代码

在10-II的基础上修改一下代码：

int
numWays (int n)
{
  if (n == 0 || n == 1)
    return 1;
  int a = 0, b = 1, c;
  for (int i = 0; i < n; ++i)
    {
      c = (a + b) % 1000000007;
      a = b;
      b = c;
    }
  return b % 1000000007;
}

结果

执行结果：通过

执行用时：0 ms, 在所有 C 提交中击败了100.00%的用户

内存消耗：5.1 MB, 在所有 C 提交中击败了41.94%的用户

备注

这道题是不是只是为了题目而题目，定义n=0的时候，结果为1，并不存在实际上的意义。一如很多只求算法，而不求使用性的题目皆是如此。