猴子爬山问题以及拓展奇偶步问题_有一只猴子可以向上跳1个台阶,也可以向上跳2个台阶,还可以向上跳3个台阶,有n个台

猴子爬山问题

问题描述

1. 猴子爬山，一步可以爬1级也可以爬2级，从第0个台阶爬到第n个台阶，总共有多少种方案？
2. 猴子爬山，一步可以爬1级也可以爬2级，从第0个台阶爬到第n个台阶共用了偶数步，总共有多少种方案？
3. 猴子爬山，一步可以爬1级也可以爬2级，从第0个台阶爬到第n个台阶共用了奇数步，总共有多少种方案？

解题思路即编码

总数方案数

思路

1. 定义一维数组f[n + 1] ，f [n]表示爬到第n个台阶的方案;
2. 爬到第n个台阶可以从第n-1个台阶爬1级，也可以从第n-2个台阶爬2级；
3. 得到递推关系f [i] = f [i– 1] + f [i– 2].

代码

public static int sum(int n) {
     if (n == 1) {
         return 1;
     }
     int[] f = new int[n + 1];
     f[1] = 1;
     f[2] = 2;
     for (int i = 3; i <= n; i++) {
         f[i] = f[i - 1] + f[i - 2];
     }
     return f[n];
}
1
2
3
4
5
6
7
8
9
10
11
12

该代码的空间复杂度为O(n)，可以降低空间复杂度。
以下这篇文章中有解决方案，此处不在介绍。
文章链接

偶数步数方案数

思路

1. 定义二维数组f [n + 1][2] ，f [n][0]表示用偶数步爬到第n个台阶的方案，f [n][1]表示用奇数步爬到第n个台阶的方案。
2. 用偶数步爬到第n个台阶，就是用奇数步爬到第n-1个台阶再爬一级，也可以是用奇数步爬到第n-2个台阶再爬两级。
3. 因为计算偶数步爬到n个台阶时，需要用到奇数步爬到n-1个台阶的方案数和用奇数步爬到n-2个台阶的方案数，所以计算偶数步的同时需要计算奇数步。
4. 得到递推关系式：
   • f[i][0] = f [i - 1][1] + f [i - 2][1].
   • f[i][1] = f [i - 1][0] + f [i - 2][0].

代码

public static int sum(int n) {
    if (n == 1) {
        return 0;
    }
    //f[n][0]表示偶数 f[n][1]表示奇数
    int[][] f = new int[n + 1][2];
    f[1][0] = 0; f[1][1] = 1;
    f[2][0] = 1; f[2][1] = 1;
    for (int i = 3; i <= n; i++) {
        //偶数
        f[i][0] = f[i - 1][1] + f[i - 2][1];
        //奇数
        f[i][1] = f[i - 1][0] + f[i - 2][0];
    }
    return f[n][0];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

奇数步数方案数

思路

1. 定义二维数组f [n + 1][2] ，f [n][0]表示用偶数步爬到第n个台阶的方案，f [n][1]表示用奇数步爬到第n个台阶的方案。
2. 用奇数步爬到第n个台阶，就是用偶数步爬到第n-1个台阶再爬一级，也可以是用偶数步爬到第n-2个台阶再爬两级。
3. 因为计算奇数步爬到n个台阶时，需要用到偶数步爬到n-1个台阶的方案数和用偶数步爬到n-2个台阶的方案数，所以计算奇数步的同时需要计算偶数步。
4. 得到递推关系式：
   • f[i][0] = f [i - 1][1] + f [i - 2][1].
   • f[i][1] = f [i - 1][0] + f [i - 2][0].

代码

public static int sum(int n) {
    if (n == 1) {
        return 1;
    }
    //f[n][0]表示偶数 f[n][1]表示奇数
    int[][] f = new int[n + 1][2];
    f[1][0] = 0; f[1][1] = 1;
    f[2][0] = 1; f[2][1] = 1;
    for (int i = 3; i <= n; i++) {
        //偶数
        f[i][0] = f[i - 1][1] + f[i - 2][1];
        //奇数
        f[i][1] = f[i - 1][0] + f[i - 2][0];
    }
    return f[n][1];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

运行结果

读者若发现错误，请及时与笔者联系，万分感谢^ v ^ ！！！