FilesExpand file tree

 master

/

offer102.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

30 lines (29 loc) · 970 Bytes

 master

/

offer102.java

Copy path

Top

File metadata and controls

• Code
• Blame

30 lines (29 loc) · 970 Bytes

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

/**

* [10-II] 青蛙跳台阶问题

*

* 题目: 一只青蛙一次可以跳上 1 级台阶, 也可以跳上 2 级台阶. 求该青蛙跳上一个 n 级的台阶总共有多少种跳法.

* (答案需要取模 1e9 + 7 (1000000007))

*

* 思路: 动态规划, f(i) 表示 i 个台阶一共有多少种跳法;

* 状态转移方程: f(i) = f(i - 1) + f(i - 2).

* 与 [10-I] 斐波那切数列的不同在于, 此题的 f(0) = 1, f(1) = 1(斐波那切数列的 f(0) = 0, f(1) = 1).

*/

class Solution {

/**

* 时间复杂度: O(n)

* 空间复杂度: O(1)

*/

public int numWays(int n) {

if (n <= 1) {

return 1;

}

int pre = 1, succ = 1;

for (int i = 2; i <= n; i++) {

// state transition equation: f(i) = f(i - 1) + f(i - 2).

int fib = (pre + succ) % (int) (1e9 + 7);

pre = succ;

succ = fib;

}

return succ;

}

}