FilesExpand file tree

 master

/

offer103.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

22 lines (21 loc) · 796 Bytes

 master

/

offer103.java

Copy path

Top

File metadata and controls

• Code
• Blame

22 lines (21 loc) · 796 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

/**

* [10-III] 变态跳台阶

*

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

*

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

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

* ==> f(n) = 2 * f(n - 1)

* f(n - 1) = f(n - 2) + f(n - 3) + ... + f(0)

*

*/

public class Solution {

public int JumpFloorII(int n) {

int dp = 1;

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

// state transition equation: f(n) = 2 * f(n - 1).

dp = 2 * dp;

}

return dp;

}

}