【题目】
You are climbing a stair case. It takesnsteps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
【题意】
爬楼梯。爬到楼顶需要n步。
每一次你都可以爬一步或者爬两步,问有多少种方式爬到楼顶?
【分析】
设 f (n) 表示爬 n 阶楼梯的不同方法数,为了爬到第 n 阶楼梯,有两个选择:
• 从第 n - 1 阶前进 1 步;
• 从第 n - 2 阶前进 2 步;
因此,有 f (n) = f (n - 1) + f (n - 2)。
这是一个斐波那契数列。
详细分析请参考:编程之美之斐波那契数列
【代码1】
// 递归
class Solution {
public:
int climbStairs(int n) {
return Fibonacci(n);
}
private:
int Fibonacci(int n){
if(n <= 2){
return n;
}
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
};
【代码2】
/*********************************
* 日期:2014-01-23
* 作者:SJF0115
* 题号: Climbing Stairs
* 来源:http://oj.leetcode.com/problems/climbing-stairs/
* 结果:AC
* 来源:LeetCode
* 总结:
**********************************/
#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;
// 迭代,时间复杂度 O(n),空间复杂度 O(1)
class Solution {
public:
int climbStairs(int n) {
int prev = 0;
int cur = 1;
for(int i = 1; i <= n ; ++i){
int tmp = cur;
cur = prev + cur;
prev = tmp;
}
return cur;
}
};
int main() {
Solution solution;
int result;
result = solution.climbStairs(40);
printf("Result:%d\n",result);
return 0;
}
【代码3】
/*********************************
* 日期:2014-01-23
* 作者:SJF0115
* 题号: Climbing Stairs
* 来源:http://oj.leetcode.com/problems/climbing-stairs/
* 结果:AC
* 来源:LeetCode
* 总结:
**********************************/
#include <iostream>
#include <stdio.h>
#include <math.h>
using namespace std;
// 数学公式,时间复杂度 O(1),空间复杂度 O(1)
class Solution {
public:
int climbStairs(int n) {
double s = sqrt(5);
return floor((pow((1+s)/2, n+1) + pow((1-s)/2, n+1))/s + 0.5);
}
};
int main() {
Solution solution;
int result;
result = solution.climbStairs(40);
printf("Result:%d\n",result);
return 0;
}
【代码4】
/*********************************
* 日期:2014-01-24
* 作者:SJF0115
* 题号: Climbing Stairs
* 来源:http://oj.leetcode.com/problems/climbing-stairs/
* 结果:AC
* 来源:LeetCode
* 总结:
**********************************/
#include <iostream>
#include <stdio.h>
using namespace std;
class Solution {
public:
//Fibonacci数列
int climbStairs(int n) {
if(n == 0){
return 0;
}
int A[2][2] = {1,1,1,0};
//初始为单位矩阵
int Matrix[2][2] = {1,0,1,0};
//n = n - 1;
for(; n ;n >>= 1){
//奇偶
if(n&1){
MatrixMulti(Matrix,A);
}//if
MatrixMulti(A,A);
}//for
return Matrix[0][0];
}
private:
//矩阵乘法
void MatrixMulti(int matrix[2][2],int matrix2[2][2]){
int a = matrix[0][0] * matrix2[0][0] + matrix[0][1] * matrix2[1][0];
int b = matrix[0][0] * matrix2[0][1] + matrix[0][1] * matrix2[1][1];
int c = matrix[1][0] * matrix2[0][0] + matrix[1][1] * matrix2[1][0];
int d = matrix[1][0] * matrix2[0][1] + matrix[1][1] * matrix2[1][1];
matrix[0][0] = a;
matrix[0][1] = b;
matrix[1][0] = c;
matrix[1][1] = d;
}
};
int main() {
Solution solution;
int result;
for(int i = 1;i < 10;i++){
result = solution.climbStairs(i);
printf("Result:%d\n",result);
}
return 0;
}
分享到:
相关推荐
leetcode 走踏板爬楼梯 Leetcode 问题 70 你正在爬楼梯。 需要n步才能到达顶部。 每次您可以爬 1 或 2 个台阶。 你可以通过多少种不同的方式登上顶峰? 示例 1: Input: 2 Output: 2 Explanation: There are two ...
leetcode 走踏板爬楼梯 你正在爬楼梯。 需要n步才能到达顶部。 每次您可以爬 1 或 2 个台阶。 你可以通过多少种不同的方式登上顶峰? 注意:给定 n 将是一个正整数。 示例 1: 输入:2 输出:2 解释:有两种方法可以...
leetcode 走踏板爬楼梯 力码练习 你正在爬楼梯。 需要n步才能到达顶部。 每次您可以爬 1 或 2 个台阶。 你可以通过多少种不同的方式登上顶峰? 注意:给定 n 将是一个正整数。
leetcode 走踏板LeetCode_70--爬楼梯 你正在爬楼梯。 需要n步才能到达顶部。 每次您可以爬 1 或 2 个台阶。 你可以通过多少种不同的方式登上顶峰? 注意:给定 n 将是一个正整数。 示例 1: 输入:2 输出:2 说明:...
leetcode怎么销号 LeetCode-Solutions :green_heart:My own LeetCode solutions No. Problem LeetCode 力扣 Python Go Solution Difficulty Tag ...Climbing Stairs Easy 动态规划 0075 Sort Colors M
leetcode 答案LeetCode LeetCode in Swift 这个Repo 用来存下我在LeetCode 解题的原始档,包含解题中遇到的错误,也包含解出AC 的答案, ...Climbing Stairs Easy #83 Remove Duplicates from Sorted L
Min Cost Climbing Stairs [746]2. Best Time to Buy and Sell Stock [121]3. Climbing Stairs [70]4. Maximum Subarray [53]5. House Robber [198]6. Range Sum Query - Immutable [303]7. Counting Bits [338]8. ...
Leetcode扑克 ...Climbing Stairs 变态跳台阶 矩形覆盖 二进制中1的个数 191. Number of 1 Bits 数值的整数次方 50. Pow(x, n) 调整数组顺序使奇数位于偶数前面 905. Sort Array By Parity 链表中倒数第
Climbing Stairs 01. two sum 经典例题: 1. 二维数组查找问题。限制条件为左到右递增,上到下递增。 2. KMP算法实现 UVA problem 100 - The 3n + 1 problem 151 - Power Crisis -> 约瑟夫问题DP 问题 10607 - ...
leetcode写题闪退 #*的多少代表此题的有意思程度 有几题第一次写的时候思绪比较混乱: *****Regular Expression Matching 2014.10.29 对于Find Minimum in Rotated Sorted Array II 和 Find Minimum in Rotated ...
Stairs](./leetcode/动态规划-Climbing Stairs.java) [动态规划-Decode Ways](./leetcode/动态规划-Decode Ways.java) [动态规划-Distinct Subsequences](./leetcode/动态规划-Distinct Subsequences.java) [动态...
Climbing Stairs 0719. Find K-th Smallest Pair Distance 0714. Best Time to Buy and Sell Stock with Transaction Fee 0713. 乘积小于K的子数组 0695. 岛屿的最大面积 0674. 最长连续递增序列 0673. 最长递增子...
leetcode 【演示记录】 报告 展示 2017/03/06 1.二和,167.二和二 2107/03/06 15.3 总和,16.3 总和最近,18.4 总和,11.最多水的容器 2017/03/09 62.Unique Paths, 63.Unique Paths II, 64.Minimum Path Sum 2017/...
Climbing Stairs 121 买卖股票的最佳时机 Best Time to Buy and Sell Stock 122 买卖股票的最佳时机 Ⅱ Best Time to Buy and Sell StockⅡ 123 买卖股票的最佳时机 Ⅲ Best Time to Buy and Sell StockⅢ 188 买卖...
70.爬楼梯 (Climbing Stairs) 83.删除排序链表中的重复元素 (Remove Duplicates from Sorted List) 88.合并两个有序数组 (Merge Sorted Array) 100.相同的树 (Same Tree) 104.二叉树的最大深度 (Maximum Depth of ...
70.Climbing Stairs 121.Best Time to Buy and Sell Stock 122.Best Time to Buy and Sell Stock II 123.Best Time to Buy and Sell Stock III 141.Linked List Cycle 142.Linked List Cycle II 188.Best Time to ...
min-cost-climbing-stairs.cpp 第 4 天: [待办事项] leetcode/1143。 最长公共子序列.cpp 第 5 天: [待办事项] leetcode/221。 最大平方.cpp 利特代码/85。 最大矩形.cpp 第 6 天: leetcode/97. 交错字符串.cpp ...
Climbing Stairs Set Matrix Zeroes API System.arrayCopy 刷题顺序 TOP100 其中算法,主要是以下几种: 基础技巧:分治、二分、贪心 排序算法:快速排序、归并排序、计数排序 搜索算法:回溯、递归、深度优先遍历,...
Climbing Stairs 一开始用传统的递归解题,结果TL了。看了下Dscuss,搜索了一下,发现这道居然就是典型的动态规划题,用哈希把子问题的答案记录了就能节省大量的运行时间。 Linked List Cycle 判断链表是否有环。...
Climbing Stairs] [101. Symmetric Tree] [104. Maximum Depth of Binary Tree] [121. Best Time to Buy and Sell Stock] [167. Two Sum II - Input array is sorted] Medium [2. Add Two Numbers]