LeetCode初级算法--动态规划01:爬楼梯
LeetCode初级算法--动态规划01:爬楼梯
搜索微信公众号:'AI-ming3526'或者'计算机视觉这件小事' 获取更多算法、机器学习干货
csdn:https://blog.csdn.net/baidu_31657889/
csdn:https://blog.csdn.net/abcgkj/
github:https://github.com/aimi-cn/AILearners
一、引子
这是由LeetCode官方推出的的经典面试题目清单~
这个模块对应的是探索的初级算法~旨在帮助入门算法。我们第一遍刷的是leetcode推荐的题目。
查看完整的剑指Offer算法题解析请点击github链接:
github地址
二、题目
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
注意:给定 n 是一个正整数。
示例1:
输入: 2
输出: 2
解释: 有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
示例2:
输入: 3
输出: 3
解释: 有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
1、思路
首先我可以确切的告诉你,这种简单的爬楼梯也是一个斐波那契数列,不信你自己从简单的数1,2,3..自己推论一下。
接着,我们来讨论一般情况。我们把n级台阶时的跳法看成是n的函数,记为f(n)。当n>2时,第一次跳的时候就有两种不同的选择:一是第一次只跳1级,此时跳法数目等于后面剩下的n-1级台阶的跳法数目,即为f(n-1);另外一种选择是跳一次跳2级,此时跳法数目等于后面剩下的n-2级台阶的跳法数目,即为f(n-2)。因此n级台阶的不同跳法的总数f(n)=f(n-1)+f(n-2)。分析到这里,我们不难看出这实际上就是斐波那契数列了。
2、编程实现
python
class Solution(object):
def climbStairs(self, n):
"""
:type n: int
:rtype: int
"""
if n == 1:
return 1
a = 1
b = 1
for i in range(1,n):
a , b = b , a+b
return b
AIMI-CN AI学习交流群【1015286623】 获取更多AI资料
分享技术,乐享生活:我们的公众号计算机视觉这件小事每周推送“AI”系列资讯类文章,欢迎您的关注!
本文由博客一文多发平台 OpenWrite 发布!
最新文章
- [转]用Middleware给ASP.NET Core Web API添加自己的授权验证
- Coursera-Getting and Cleaning Data-Week3-dplyr+tidyr+lubridate的组合拳
- 9款一键快速搭建PHP运行环境的好工具
- Xcode 8.2 想使用插件 怎么办? 教你科学的使用插件
- Nodejs学习总结 -Express入门(一)
- MyEclipse调用Matlab打包函数
- oracle10g库连接报错
- Struts2常量的具体用法实例(一)
- Spring个人总结
- Git学习笔记:Git基础
- c语言,链表
- java8 stream ,filter 等功能代替for循环
- UVa 10551 - Basic Remains
- javaEE-string家族三大流氓
- Azure 认知服务 (4) 计算机视觉API - 读取图片中的文字 (OCR)
- I/O复用中的 select poll 和 epoll
- Python3基础教程2——Python的标准数据类型
- WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED! --主机密钥验证失败
- laravel简书(1)
- selenium_unittest框架,TestCase引用
热门文章
- python+selenium一:对浏览器的常规操作
- Anroid逆向学习从编写so到静动态调试分析arm的一次总结
- charles 访问控制设置
- python解释器安装和变量配置
- 实操:Could not autowire No beans of 'FastDFS Client' type found 的解决方法
- Spring Cloud 全链路追踪实现
- C++——数组与字符串
- mysql操作遇到的坑(第二版)
- mysql创建用户和权限管理
- Spring Boot 2.X(二):集成 MyBatis 数据层开发