求助｜青蛙跳荷叶问题

问题描述： 笔试遇到的一道算法题，没有全 AC，求指点。

题目大意为，河面上有编号 1 到 N 的 N 片荷叶，青蛙目前在 1 号荷叶，目的地是跳到 N 号荷叶。它有两种跳法：1. 跳到相邻荷叶，2. 跳过相邻荷叶跳到下一片（从 1 直接跳到 3）。可以向左跳也可以向右跳。但是有一个限制是落到一片荷叶上再跳走后，这片荷叶就沉入水底，不能再跳回来了。问跳到 N 有多少种跳法。

举例：N = 4，有 4 跳法，1234，134，124，1324。
N 的范围是 1 到 1000000000 （忘记多少个零了），另外还输入一个 M，用于对结果取模，M 的上限是 1000000007。

思考方向： 这应该是一道典型的动态规划，我当时的想法是跳到 i 有三种跳法，从 i - 1 跳 1 个步长到 i，从 i - 2 跳 2 个步长到 i，或从 i - 3 先跳 2 个步长到 i - 1，再往回跳到 i - 2，再跳到 i。定义 dp[i] 是从 1 跳到 i 的跳法数，那状态转移就是：dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];

需要帮助的地方： 最后是 36% AC，有两个问题求教

1. 状态转移有没有问题，是不是有遗漏或者重复的情况？
2. 是不是 int 类型大数溢出了？（我用的 Java），我只在最后返回的时候 dp[N] % M，是不是应该再状态转移的时候给每个 dp[] 都 % M 才对？

谢谢！