Climbing Stairs

Problem description
Level: easy

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

Analysis:
As it is asking for count #, we can consider trying DP

state: count how many distinct ways in position i use f(i)
Function: f(i) = f(i-1) + f(i-2) To climb to I, it can be from i-1 and i-2
Initialize: f(1) = 1 f(2) = 2
final: f(n)

Solution 1:

Solution 2:

Share on FacebookShare on Google+Tweet about this on TwitterShare on LinkedInShare on RedditShare on StumbleUponEmail this to someoneShare on TumblrDigg this

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">