700字范文 > N级台阶一次上1级或2级或3级或M级总共有多少种走法

N级台阶一次上1级或2级或3级或M级总共有多少种走法

时间：2022-04-12 13:02:24

思路

先分析最简单的，也就是每次要不上1级，要么上2级。

这个问题需要反过来思考才能比较容易的找到规律。总共有N级台阶，因为每次要么上1级要么上2级，因此对于第N级台阶来说，它的前一步要么是在N-1级处要么是在N-2级处。在N-1级处时上1级到N级台阶，在N-2级处时上2级到N级台阶。因此，可以用公式表示为f(n)=f(n-1)+f(n-2)，其中f(n)表示从第一级开始到第n级有多少种走法。当然，除了逆向思考外，也可以正面寻找规律。因为每次要不上1级要不上2级，那么在刚开始时，有两种选择，1或2，如果上1级，那么还剩n-1级，如果上2级，那么还剩n-2级，所以跟逆向思维一样得到f(n)=f(n-1)+f(n-2)。这就是一个典型的递归问题了。像这种公式，在数列中有一个比较著名的数列叫做“斐波那契数列”。

一次走1级或2级的总走法问题

解法一：递归法（复杂度O(N!) ）

public class Main {public static void main(String[] args) {long start = System.currentTimeMillis();fun(10);System.out.println("n=10时运行时间："+(System.currentTimeMillis() - start));start = System.currentTimeMillis();fun(30);System.out.println("n=30时运行时间："+(System.currentTimeMillis() - start));start = System.currentTimeMillis();fun(40);System.out.println("n=40时运行时间："+(System.currentTimeMillis() - start));}public static int fun(int stair){if(stair == 1){return 1;}else if(stair == 2){return 2;}else{return fun(stair - 1)+fun(stair - 2);}}}

输出结果

可以看到当n增大时，时间复杂度会程指数级增加，这样递归算法就崩溃了。因为递归算法会有大量的重复计算，时间复杂度太高O(n!)。因此可以采用将之前计算的结果保存到map中，在后续需要用的时候直接取出来用而不用重复计算（动态规划）。这样时间复杂度就大大降低了。

解法二：动态规划法

public static int climbStairs(int n,Map<Integer,Integer> map){if(n <= 0)return 0;if(n <= 2)return n;if(map.containsKey(n)){return map.get(n);}else{int temp = climbStairs(n - 1,map) + climbStairs(n - 2,map);map.put(n, temp);return temp;}}

除了上面的递归法和动态规划法之外，这里还有另外一种方法来计算每次上1级或2级时的总走法——循环法（自命名的）。根据递归的过程可知，最终都会转化成计算f(1)或f(2)，最后结果是a个f(1)与b个f(2)*2的和。因此可以先通过循环的方式求a和b，最后直接计算即可。先通过下表找a和b与n之间的规律：

可以发现，第n项的a和b分别是其前两项的a的和。这就简单了，下面是循环方式的代码。

解法三：循环法

public static int climbStairs2(int n){if(n == 0)return 0;if(n == 1)return 1;if(n == 2)return 2;int lastF1 = 1,lastF2 = 0,nextF1 = 0,nextF2 = 1;int resultF1 = 0,resultF2 = 0;for(int i=3;i<=n;i++){resultF1 = lastF1 + nextF1;resultF2 = lastF2 + nextF2;lastF1 = nextF1;lastF2 = nextF2;nextF1 = resultF1;nextF2 = resultF2;}return resultF1+2*resultF2;}

上述三种方法在n=44时的运行时间比较如下：

一次走1级或2级或3级的总走法

这种情况只比一次走1级或2级的多了一个选择3而已，因此也可以直接使用递归的方式实现。

解法一：递归法

输出结果

同样的，递归方法的时间复杂度太高，需要考虑使用其他的方法实现。对于是否能够像解只有1或2级的那样找到a,b,c与n的规律进行求解，我没有尝试，感觉应该是有规律的（感兴趣的可以找一下规律）。这里只使用了动态规划法来降低时间复杂度。

解法二：动态规划法

public static int fun1(int stair,Map<Integer,Integer> map){if(stair == 1){return 1;}else if(stair == 2){return 2;}else if(stair == 3){return 4;//3级台阶总共有4种走法}else if(map.containsKey(stair)){return map.get(stair);}else{int temp = fun1(stair - 1,map)+fun1(stair - 2,map)+fun1(stair - 3,map);map.put(stair, temp);return temp;}}

上述两种方法在n=30时的运行时间比较如下：

问题拓展：一次至少上1级，至多上m级，有多少种走法？

这个问题是此类问题的最一般形式。就是每次的步数不固定，有m种可能。跟前面的类似，也可以使用递归的方式解决。只是这里因为步数不固定，所以要用for循环来对每一种可能的步数进行递归操作。当剩下的台阶数小于m时，那么每次就有剩余台阶数种可能的选择。直到最终剩余台阶数为0时，说明一种走法结束了。因此此递归函数的终止条件就是剩余台阶数为0。

同样的，为了减少重复计算，采用map保留以前的计算结果。

动态规划法

public static int countScheme(int n, int m, Map<Integer, Integer> map) {int count = 0;if (n== 0) {return 1;}if (map.containsKey(n)) {return map.get(n);} else if (n>= m) {for (int i = 1; i <= m; i++) {count += countScheme1(n- i, m, map);}} else {count += countScheme(n, n, map);}map.put(n, count);return count;}