算法题-跳格子有多少种走法_跳格子算法设计

问题描述：

假设你正在玩跳格子（所有格子排成一个纵列）游戏。需要 跳完n 个格子你才能抵达终点。
每次你可以跳 1 或 2 个格子。你有多少种不同的方法可以到达终点呢？
注意：给定 n 是一个正整数。

算法思路：

这是一道很经典的问题，题不难，但是是理解“递推”和“递归”两种思想的很好的一道算法题。

递归是自上到下递归，但求解还是先求子问题

递推是先求小问题，次大问题可以通过子问题获得

解答

解法一：递推(动态规划法)

import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.valueOf(br.readLine());
        if(n == 1) {
            System.out.println(1);
        }
        int[] a = new int[n + 1];
        a[0] = 1;
        a[1] = 1;
        for(int i = 2; i <= n; i++) {
            a[i] = a[i - 1] + a[i - 2];
        }
        System.out.println(a[n]);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

解法二：递归

import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.valueOf(br.readLine());
        System.out.println(recursive(n));
    }
    
    private static int recursive(int n) {
        if(n == 1) {
            return 1;
        }
        if(n == 2) {
            return 2;
        }
        return recursive(n - 1) + recursive(n - 2);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19