Description
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?
Example
Given an example n=3 , 1+1+1=2+1=1+2=3
return 3
又是一道动态规划类的题目,马上做个专题总结一下。先看一下这个题目,爬楼梯问题,爬楼梯的时候,一次跨一个台阶,或者一次跨两个台阶。我们先从最基本的情况来看:
(1)只有一个台阶:那只有一种走法。(2)大于等于2的时候:那就要分情况讨论了,如下图所示:
如果想要到达k号台阶,可以选择从k-1号踏上去,也可以选择从k-2号跨过去,但是要先从第0号台阶走到第k-1或者k-2号台阶。走到k-1的方案总数,加上走到k-2的方案总数,就是走到k的方案总数。可以定义一个数组kinds,用kinds[k]来保存走到第k号台阶的方案总数,那么 kinds[k]=kinds[k-1]+kinds[k-2];(其中k>=2)。代码如下:
public class Solution {
/**
* @param n: An integer
* @return: An integer
*/
public int climbStairs(int n) {
// write your code here
if(n==0)
return 0;
if(n==1)
return 1;
int []kinds=new int[n];
//初始化第0号和第1号台阶
kinds[0]=1;
kinds[1]=2;
for(int i=2; i<n; i++){
kinds[i]=kinds[i-1]+kinds[i-2];
}
//最后一号便是爬到顶的方案总数
return kinds[n-1];
}
}
其实一开始也想到用递归的方法,不过由于递归的次数太多,报了*栈溢出的错误,源代码如下:
public class Solution {
/**
* @param n: An integer
* @return: An integer
*/
public int climbStairs(int n) {
// write your code here
if(n==0)
return 0;
if(n==1)
return 1;
if(n==2)
return 2;
return climbStairs(n-1)+climbStairs(n-2);
}
}
111. Climbing Stairs 【LintCode easy】的更多相关文章
-
70. Climbing Stairs【leetcode】递归,动态规划,java,算法
You are climbing a stair case. It takes n steps to reach to the top. Each time you can either climb ...
-
LintCode 111 Climbing Stairs
这道题参考了这个网址: http://blog.csdn.net/u012490475/article/details/48845683 /* 首先考虑边界情况,当有1层时,有一种方法. 然后再看2层 ...
-
【LintCode&#183;容易】用栈模拟汉诺塔问题
用栈模拟汉诺塔问题 描述 在经典的汉诺塔问题中,有 3 个塔和 N 个可用来堆砌成塔的不同大小的盘子.要求盘子必须按照从小到大的顺序从上往下堆 (如:任意一个盘子,其必须堆在比它大的盘子上面).同时, ...
-
【LintCode&#183;入门】斐波那契数列
斐波那契数列 描述 查找斐波纳契数列中第 N 个数. 所谓的斐波纳契数列是指: 前2个数是 0 和 1 . 第 i 个数是第 i-1 个数和第i-2 个数的和. 斐波纳契数列的前10个数字是: 0, ...
-
【LintCode&#183;容易】字符串置换
字符串置换 描述: 给定两个字符串,请设计一个方法来判定其中一个字符串是否为另一个字符串的置换. 置换的意思是,通过改变顺序可以使得两个字符串相等. 样例: "abc" 为 &qu ...
-
451. Swap Nodes in Pairs【LintCode java】
Description Given a linked list, swap every two adjacent nodes and return its head. Example Given 1- ...
-
445. Cosine Similarity【LintCode java】
Description Cosine similarity is a measure of similarity between two vectors of an inner product spa ...
-
433. Number of Islands【LintCode java】
Description Given a boolean 2D matrix, 0 is represented as the sea, 1 is represented as the island. ...
-
423. Valid Parentheses【LintCode java】
Description Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine ...
随机推荐
-
Linux 下SVN服务器搭建
系统环境 RHEL5.4最小化安装(关iptables,关selinux) + ssh + yum 一,安装必须的软件包. yum install subversion (SVN服务器 ...
-
linux文件锁
http://blog.chinaunix.net/uid-25324849-id-3077304.html 在SHELL中实现文件锁,有两种简单的方式.(1)一是利用普通文件,在脚本启动时检查特定文 ...
-
iOS基础 - 数据库-SQLite
一.iOS应用数据存取的常用方式 XML属性列表 —— PList NSKeyedArchiver 归档 Preference(偏好设置) SQLite3 Core Data(以面向对象的方式操作数据 ...
-
Error Code: 1054. Unknown column &#39;age&#39; in &#39;user&#39;
1.错误描述 10:28:20 alter table user modify age int(3) after sex Error Code: 1054. Unknown column 'age' ...
-
如何删除pagefile.sys
经常使用电脑的用户就会发现系统自带了虚拟内存文件pagefile.sys,若是电脑出现内存不足情况,其就会调用虚拟内存来执行程序,以防止系统内存崩溃.不过,虚拟内存没有真实的内存读取速度快,而且会占用 ...
-
Python【每日一问】02
问:列表 test = [1,2,3,1,3,4,5,67,7,8,54,1,2,3,4,5,6],如何删除该列表的重复元素? 方法1:利用集合的不重复性 # 利用集合的不重复性 test = [1, ...
-
JS验证码邮件
js var time = 30; var canSend = true; function f5() { if (canSend) {//判断是否要ajax发送刷新验证码 验证码在后台刷新 //al ...
-
ROADS POJ - 1724(分层最短路)
就是在最短路的基础上 多加了一个时间的限制 , 多一个限制多一维就好了 记住 分层最短路要用dijistra !!! #include <iostream> #include < ...
-
win怎么设置最快捷的下滑关机
win怎么设置最快捷的下滑关机 1.在C:\Windows\System32下找到SlideToShutDown.exe文件发送一份到桌面快捷方式 2.右键此快捷方式--属性--更换图表--更换一个自 ...
-
openstack 开启 spice远程连接
openstack 默认开的远程控制是novnc 这里是用kolla初建的openstack nova_console vi /etc/kolla/globals.yml ... # Valid op ...