LCR 127.跳跃训练

发表于2024-03-29更新于2024-03-29

跳跃训练

题目

图 0

我的求解

这道题我很有印象，和爬楼梯是同一个意思。就是要用到动态规划。逻辑在于我要到达第n个格子的方法，等于我要到达第n-1个格子的方法加到达n-2个格子的方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
var trainWays = function(num) {
  //和爬楼梯很像，是动态规划的题目
  //dp[i]表示跳到第i个台阶的方法数
  let dp = new Array(num + 1).fill(0)
  dp[0] = 1
  dp[1] = 2
  //这里有一些特殊情况，第一种是在程序提交不同过的例子中发现的，
  if (num === 0) return dp[0]
  //第二种就是只有一个格子
  if (num === 1) return dp[0]
  //第三种只有两个格子的情况。
  if (num === 2) return dp[1]
  else {
    for (let i = 2; i < num; i++) {
      //别忘了题目要求的取模
      dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007
    }
    return dp[num - 1]
  }
};