您现在的位置是:首页 > 后台技术 > 数据结构与算法数据结构与算法
爬楼梯(图文)
第十三双眼睛2023-11-25【数据结构与算法】人已围观
简介爬楼梯
思路:登上第一级台阶,需要1种方法,登上第二级台阶,需要2种方法,登上第三集台阶,等于登上第一级台阶,然后登两级,也可以登上第二级台阶,然后登一级,总结出如下规律,登上第n级台阶等于登上第 n-1级台阶的方法 加上登上第n - 2级台阶的方法,因此可以用递归。代码如下:
在递归的过程中,有重复计算的,比如计算10和9的时候,8都是计算过的,因此没有必要重复计算,可以用一个数组存起来。代码如下:
第三种思路:不难发现,这就是一个斐波那契数列,从第三个元素开始,每个元素等于前两个元素之和,因此,依次计算,最终就能得到目标值。代码如下:
上面的代码中,我们初始化了一个数组,其实没有必要,因为只要能记录两个,就能推出来第三个,因此用3个变量即可。代码如下:
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的平方根(图文)
下一篇:删除排序链表中的重复元素(图文)