问题大致是这样的:50格楼梯,每次可以上1个或2个台阶,问爬完楼梯方法的可能性有几种。
答:简单的递归可以算出,但是时间复杂度是指数级的;好的做法是可以在递归中,把中间结果缓存起来,这样可以避免递归中的重复计算,提高了运算速度,该算法复杂度是线性级的o(n)。
/*
* There are a certain number of steps of a stair, one can be up stair
* by 1 step or 2 steps for each time. How many possibilities one can
* go up stairs?
*
* Answer, if only using recursion, the time complex is index grade while
* catching each middle result changes it to linear grade.
*/
package com.algo;
public class Stairs {
long[] results;
public long calculateApproaches(int stairCount) { // 1 - 50
if (results == null) results = new long[stairCount];
if (stairCount < 0) return 0;
if (stairCount == 0) return 1;
if (results[stairCount - 1] != 0) return results[stairCount - 1];
long temp = 0;
if (stairCount == 1) {
temp = 1;
} else {
temp = calculateApproaches(stairCount - 1) + calculateApproaches(stairCount - 2);
}
results[stairCount - 1] = temp;
return temp;
}
public static void main(String[] args) {
System.out.println("n=1 : " + new Stairs().calculateApproaches(1));
System.out.println("n=2 : " + new Stairs().calculateApproaches(2));
System.out.println("n=3 : " + new Stairs().calculateApproaches(3));
System.out.println("n=4 : " + new Stairs().calculateApproaches(4));
System.out.println("n=5 : " + new Stairs().calculateApproaches(5));
System.out.println("n=6 : " + new Stairs().calculateApproaches(6));
System.out.println("n=40 : " + new Stairs().calculateApproaches(40));
System.out.println("n=50 : " + new Stairs().calculateApproaches(50));
}
}
分享到:
相关推荐
本文实例讲述了Python3爬楼梯算法。分享给大家供大家参考,具体如下: 假设你正在爬楼梯。需要 n 步你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢? 注意:给定 n 是一个正整数...
leetcode算法题爬楼梯,第一次提交,如有不足还请多多包涵!
//例如,楼梯有3级台阶,小明每一步可以爬1级、2级或3级,则小明一共有4种爬法。 //如果n的取值从32~36,m的取值从2~3,请写程序输出每种情况下小明有多少种爬楼梯的方法。 //输入格式:共2行数据,内容如下: /...
php 算法 爬楼梯有多少种方法
算法-爬楼梯(信息学奥赛一本通-T1204)(包含源程序).rar
上台阶算法是一个叫经典的算法,是迭代应用的体现。
某人上楼梯,他一步可以迈一个台阶,两个台阶或三个台阶,共有n个台阶,编程输出他所有可能上法。如:有4个台阶,输出应是: 1 1 1 1 1 1 2 1 2 1 1 3 2 1 1 2 2 3 1 算法设计: 给定台阶的个数n,输出所有可能的上法...
这是我用c语言写的程序,我的其他资源都是免费的,是对于c语言初学者的帮助比较大的,其中有数据结构,window编程。我也在学c语言,每当我写完一个程序,我都会免费发上来。
爬楼梯(Climbing-Stairs) 题干: 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。...这题爬楼梯算是算法题里面比较经典的。 解题思路 这题的解题思路主要有两种: 1.动态规划 2.斐波那契数
使用动态规划解决经典问题,例如爬楼梯、打家劫舍问题、单词拆分问题、买卖股票问题等 动态规划是一种算法设计技术,它通过将问题分解为重叠的子问题并利用已经解决的子问题的结果来解决更大的问题。 通常用于解决...
js代码-算法-动态规划-爬楼梯
html css js网页设计
爬楼梯.md
js代码-(算法)(动态规划)爬楼梯
在深入研究经典疯爬算法的基础上,引入了超级弹簧、计量矩阵、淬火冷却等一系列新的概念,完善了疯爬算法的理论体系,提出了一套改进疯爬算法。并将其应用于噪声环境下,交错跳频信号小波尺度图脊线的提取。在获取了...
# 题目:假设你走台阶有两种方式,一种是一步迈两个台阶,一种是一步迈一个台阶,请问你上n个台阶一共有多少种方式 # 分析过程: # g(5)=g(4)+g(3)#3,4指的是走一步或者两步后剩余的步数 # g(4)=g(3)+g(2) # g(3)=g...
问题描述:有n级台阶,一个人每次上一级或者两级,问有多少种走完n级台阶的方法。 实际情况:给定一个矩阵m,从左上角开始每次只能向右走或者向下走,最后达到右下角的位置,路径中所有数字累加起来就是路径和,返回...
一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。 答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。 示例 1: 输入:n = 2 输出:2 ...
leetcode爬楼梯排列组合解法 Data Structure and Algorithmic Practice 【任务1 - 数组与链表】 1、数组 实现一个支持动态扩容的数组 实现一个大小固定的有序数组,支持动态增删改操作 实现两个有序数组合并为一个...