LeetCode-70-Climbing Stairs

You are climbing a stair case. It takes n steps 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个台阶的话,一共有几种方法爬到顶端。

思路:

  n<=1,此时只有一种。

  n>1时,对于每一个台阶i,要到达台阶,最后一步都有两种方法,从i-1迈一步,或从i-2迈两步。

  也就是说到达台阶i的方法数=达台阶i-1的方法数+达台阶i-2的方法数。所以该问题是个DP问题。

d(0) = 1

d(1) = 1

d(2) = d(2-1) + d(2-2)

d(3) = d(3-1) + d(3-2)

……

好吧,状态转移方程其实就是Fibonacci数列。

代码实现给出两种方案吧:

python代码如下:

 1 class Solution(object):
 2     def climbStairs(self, n):
 3         """
 4         :type n: int
 5         :rtype: int
 6         """
 7         if n<=1:
 8             return 1
 9         res = []
10         res.append(1)
11         res.append(1)
12         for i in range(2,n+1):
13             res.append(res[-1]+res[-2])
14         return res[-1]

Java代码如下:

 1 public class Solution {
 2     public int climbStairs(int n) {
 3         if (n<=1)
 4             return 1;
 5 
 6         int oneStep=1,twoStep = 1,res = 0;
 7 
 8         for (int i = 2; i <= n; i++) {
 9             res = oneStep + twoStep;
10             twoStep = oneStep;
11             oneStep = res;
12         }
13         
14         return res;
15     }
16 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏聊聊技术

原 初学图论-Bellman-Ford单源

464130
来自专栏Code_iOS

OpenGL ES 2.0 (iOS)[03]:熟练图元绘制,玩转二维图形

文章的大前提是,你得有《OpenGL ES 2.0 (iOS): 一步从一个小三角开始》的基础知识。

21910
来自专栏从流域到海域

迪杰斯特拉(Dijkstra)算法求图中最短路径

迪杰斯特拉(Dijkstra )算法: 对于图G=(V,E),将图的顶点分为两组: 顶点集S:已求出的最短路径的顶点集合(初始为{v0}); 顶...

23570
来自专栏数据结构与算法

洛谷P2860 [USACO06JAN]冗余路径Redundant Paths(tarjan求边双联通分量)

题目描述 In order to get from one of the F (1 <= F <= 5,000) grazing fields (which a...

437100
来自专栏编程

数控宏程序的编程及应用

1. 什么场合会用到宏程序编程? 其实说起来宏就是用公式来加工零件,比如说椭圆,如果没有宏的话,我们要逐点算出曲线上的点,然后慢慢来用直线逼近,如果是个光洁度要...

21180
来自专栏深度学习之tensorflow实战篇

igraph软件包创建图和网络(创建邻接矩阵)

一、igraph软件包创建图和网络 igraph 是一个独立的库,底层是 C,上层有 Python 和 R 接口,主要做图和网络方面的计算,附带绘图功能。 ...

65540
来自专栏数据结构与算法

洛谷P2774 方格取数问题(最小割)

12430
来自专栏calmound

强连通专题

求割点(无向边): 所谓的割点,就是删除某个点,图便不连通了。  POJ  1523 #include<stdio.h> #include<string.h> ...

37080
来自专栏数据结构与算法

1405 奶牛的旅行

题目描述 Description 农民John的农场里有很多牧区。有的路径连接一些特定的牧区。一片所有连通的牧区称为一个牧场。但是就目前而言,你能看到至少有两个...

29380
来自专栏从流域到海域

弗洛伊德(Floyd)算法

弗洛伊德(Floyd)算法求图中两点的最短路径 佛罗依德(Floyd )算法的基本思想: 设图g用邻接矩阵法表示,求图g中任意一对顶点vi与vj间的...

28380

扫码关注云+社区

领取腾讯云代金券