您现在的位置是：首页 > 后台技术 > 数据结构与算法数据结构与算法

爬楼梯(图文)

第十三双眼睛2023-11-25【数据结构与算法】人已围观

简介爬楼梯

思路：登上第一级台阶，需要1种方法，登上第二级台阶，需要2种方法，登上第三集台阶，等于登上第一级台阶，然后登两级，也可以登上第二级台阶，然后登一级，总结出如下规律，登上第n级台阶等于登上第 n-1级台阶的方法加上登上第n - 2级台阶的方法，因此可以用递归。代码如下：

public static int method1(int num) {
   if (num == 1) {
       return 1;
   }
   if (num == 2) {
       return 2;
   }
   return method1(num - 1) + method1(num - 2);
}

在递归的过程中，有重复计算的，比如计算10和9的时候，8都是计算过的，因此没有必要重复计算，可以用一个数组存起来。代码如下：

public static int method2(int num,int[] mem) {
   if (mem[num] != 0) {
       return mem[num];
   }
   if (num == 1) {
       return 1;
   } else if (num == 2) {
       return 2;
   } else {
       mem[num] = method2(num - 1,mem) + method2(num - 2,mem);
   }
   return mem[num];
}

第三种思路：不难发现，这就是一个斐波那契数列，从第三个元素开始，每个元素等于前两个元素之和，因此，依次计算，最终就能得到目标值。代码如下：

public static int method3(int num) {
   if (num == 1) {
       return 1;
   }
   // num + 1 是因为下面舍弃掉了下标0
   int[] dp = new int[num + 1];
   dp[1] = 1;
   dp[2] = 2;
   for (int i = 3; i<=num ; i ++) {
       dp[i] = dp[i-2] + dp[i-1];
   }
   return dp[num];
}

上面的代码中，我们初始化了一个数组，其实没有必要，因为只要能记录两个，就能推出来第三个，因此用3个变量即可。代码如下：

public static int method4(int num) {
   if (num == 1) {
       return 1;
   }
   int one = 1;
   int two = 2;
   int three= 0 ;
   for (int i = 3; i<= num; i ++) {
       three = one + two;
       one = two;
       two = three;
   }
   return two;
}

Tags：

很赞哦！ ()

上一篇：x的平方根(图文)

下一篇：删除排序链表中的重复元素(图文)