{"id":26213,"date":"2017-10-26T20:30:18","date_gmt":"2017-10-26T15:00:18","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26213"},"modified":"2017-10-26T20:30:18","modified_gmt":"2017-10-26T15:00:18","slug":"java-programming-count-ways-reach-n-stair","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/java-programming-count-ways-reach-n-stair\/","title":{"rendered":"Java Programming – Count ways to reach the n stair"},"content":{"rendered":"

There are n stairs, a person standing at the bottom wants to reach the top. The person can climb either 1 stair or 2 stairs at a time. Count the number of ways, the person can reach the top.<\/p>\n

\"Stairs\"<\/p>\n

Consider the example shown in diagram. The value of n is 3. There are 3 ways to reach the top. The diagram is taken from Easier Fibonacci puzzles<\/a><\/p>\n

More Examples:<\/strong><\/p>\n

Input: n = 1\r\nOutput: 1\r\nThere is only one way to climb 1 stair\r\n\r\nInput: n = 2\r\nOutput: 2\r\nThere are two ways: (1, 1) and (2)\r\n\r\nInput: n = 4\r\nOutput: 5\r\n(1, 1, 1, 1), (1, 1, 2), (2, 1, 1), (1, 2, 1), (2, 2)<\/pre>\n
We can easily find recursive nature in above problem. The person can reach n\u2019th stair from either (n-1)\u2019th stair or from (n-2)\u2019th stair. Let the total number of ways to reach n\u2019t stair be \u2018ways(n)\u2019. The value of \u2018ways(n)\u2019 can be written as following.<\/p>\n[ad type=\u201dbanner\u201d]\n
    ways(n) = ways(n-1) + ways(n-2)\r\n<\/pre>\n
The above expression is actually the expression for Fibonacci numbers<\/a>, but there is one thing to notice, the value of ways(n) is equal to fibonacci(n+1).<\/p>\n
ways(1) = fib(2) = 1
\nways(2) = fib(3) = 2
\nways(3) = fib(4) = 3<\/p>\n
So we can use function for fibonacci numbers to find the value of ways(n). Following is Java implementation of the above idea.<\/p>\n[pastacode lang=\u201djava\u201d manual=\u201dclass%20stairs%0A%7B%0A%20%20%20%20%2F%2F%20A%20simple%20recursive%20program%20to%20find%20n\u2019th%20fibonacci%20number%0A%20%20%20%20static%20int%20fib(int%20n)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20if%20(n%20%3C%3D%201)%0A%20%20%20%20%20%20%20%20%20%20return%20n%3B%0A%20%20%20%20%20%20%20return%20fib(n-1)%20%2B%20fib(n-2)%3B%0A%20%20%20%20%7D%0A%20%20%20%20%20%0A%20%20%20%20%2F%2F%20Returns%20number%20of%20ways%20to%20reach%20s\u2019th%20stair%0A%20%20%20%20static%20int%20countWays(int%20s)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20return%20fib(s%20%2B%201)%3B%0A%20%20%20%20%7D%0A%20%0A%20%0A%20%20%20%20%2F*%20Driver%20program%20to%20test%20above%20function%20*%2F%0A%20%20%20%20public%20static%20void%20main%20(String%20args%5B%5D)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20int%20s%20%3D%204%3B%0A%20%20%20%20%20%20%20%20%20%20System.out.println(%22Number%20of%20ways%20%3D%20%22%2B%20countWays(s))%3B%0A%20%20%20%20%7D%0A%7D\u201d message=\u201dJava Program\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n[ad type=\u201dbanner\u201d]\n
Output:<\/strong>
\nNumber of ways = 5
\nThe time complexity of the above implementation is exponential (golden ratio raised to power n). It can be optimized to work in O(Logn) time using the previously discussed Fibonacci function optimizations.<\/p>\n
Generalization of the above problem
\nHow to count number of ways if the person can climb up to m stairs for a given value m? For example if m is 4, the person can climb 1 stair or 2 stairs or 3 stairs or 4 stairs at a time.<\/p>\n
We can write the recurrence as following.<\/p>\n
ways(n, m) = ways(n-1, m) + ways(n-2, m) + \u2026 ways(n-m, m)
\nFollowing is java implementation of above recurrence.<\/p>\n[pastacode lang=\u201djava\u201d manual=\u201dclass%20stairs%0A%7B%0A%20%20%20%20%2F%2F%20A%20recursive%20function%20used%20by%20countWays%0A%20%20%20%20static%20int%20countWaysUtil(int%20n%2C%20int%20m)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20if%20(n%20%3C%3D%201)%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20n%3B%0A%20%20%20%20%20%20%20%20int%20res%20%3D%200%3B%0A%20%20%20%20%20%20%20%20for%20(int%20i%20%3D%201%3B%20i%3C%3Dm%20%26%26%20i%3C%3Dn%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20%20%20res%20%2B%3D%20countWaysUtil(n-i%2C%20m)%3B%0A%20%20%20%20%20%20%20%20return%20res%3B%0A%20%20%20%20%7D%0A%20%20%0A%20%20%20%20%2F%2F%20Returns%20number%20of%20ways%20to%20reach%20s\u2019th%20stair%0A%20%20%20%20static%20int%20countWays(int%20s%2C%20int%20m)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20return%20countWaysUtil(s%2B1%2C%20m)%3B%0A%20%20%20%20%7D%0A%20%0A%20%0A%20%20%20%20%2F*%20Driver%20program%20to%20test%20above%20function%20*%2F%0A%20%20%20%20public%20static%20void%20main%20(String%20args%5B%5D)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20int%20s%20%3D%204%2Cm%20%3D%202%3B%0A%20%20%20%20%20%20%20%20%20%20System.out.println(%22Number%20of%20ways%20%3D%20%22%2B%20countWays(s%2Cm))%3B%0A%20%20%20%20%7D%0A%7D\u201d message=\u201dJava Program\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n
Output:<\/strong><\/p>\n
Number of ways = 5<\/pre>\n
The time complexity of above solution is exponential. It can be optimized to O(mn) by using dynamic programming. Following is dynamic programming based solution. We build a table res[] in bottom up manner.<\/p>\n[ad type=\u201dbanner\u201d]\n[pastacode lang=\u201djava\u201d manual=\u201dclass%20stairs%0A%7B%0A%20%20%20%20%2F%2F%20A%20recursive%20function%20used%20by%20countWays%0A%20%20%20%20static%20int%20countWaysUtil(int%20n%2C%20int%20m)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20if%20(n%20%3C%3D%201)%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20n%3B%0A%20%20%20%20%20%20%20%20int%20res%20%3D%200%3B%0A%20%20%20%20%20%20%20%20for%20(int%20i%20%3D%201%3B%20i%3C%3Dm%20%26%26%20i%3C%3Dn%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20%20%20res%20%2B%3D%20countWaysUtil(n-i%2C%20m)%3B%0A%20%20%20%20%20%20%20%20return%20res%3B%0A%20%20%20%20%7D%0A%20%20%20%20%2F%2F%20Returns%20number%20of%20ways%20to%20reach%20s\u2019th%20stair%0A%20%20%20%20static%20int%20countWays(int%20s%2C%20int%20m)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20return%20countWaysUtil(s%2B1%2C%20m)%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F*%20Driver%20program%20to%20test%20above%20function%20*%2F%0A%20%20%20%20public%20static%20void%20main%20(String%20args%5B%5D)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20int%20s%20%3D%204%2Cm%20%3D%202%3B%0A%20%20%20%20%20%20%20%20%20%20System.out.println(%22Number%20of%20ways%20%3D%20%22%2B%20countWays(s%2Cm))%3B%0A%20%20%20%20%7D%0A%7D\u201d message=\u201dJava Program\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n
Output:<\/strong><\/p>\n
Number of ways = 5<\/pre>\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"
Java Programming – Count ways to reach the n stair – Mathematical Algorithms – The time complexity of above solution is exponential. <\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,1,2139,74058],"tags":[11323,77914,77925,77877,77913,77906,77874,77890,77917,77857,77911,77886,77891,77852,77916,77923,77895,77909,77887,77856,77919,77903,77901,77898,77907,77926,77892,77897,77922,77893,77921,77896,77910,77904,77894,77900,77918,77920,77889,77912,77871,77915,77885,77908,77888,77899,77872,77924,77902,77905],"class_list":["post-26213","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-coding","category-java","category-mathematical-algorithms","tag-2-step","tag-2-step-stairs","tag-3-stairs","tag-3-step-stairs","tag-4-step-stairs","tag-5-step-stairs","tag-a-staircase-contains-three-steps","tag-benefits-of-stair-climbing","tag-best-way-to-climb-stairs","tag-climbing-stairs","tag-climbing-stairs-benefits","tag-climbing-stairs-exercise","tag-climbing-stairs-for-weight-loss","tag-climbing-stairs-problem","tag-climbing-steps","tag-exercise-stairs","tag-fibonacci-game","tag-flight-stairs","tag-how-many-stairs-should-i-climb-for-a-good-workout","tag-how-to-calculate-number-of-steps-in-stairs","tag-how-to-climb-stairs","tag-number-puzzles-with-answers","tag-rabbit-stairs","tag-recurrence-formula","tag-relations-discrete-math","tag-stair-c","tag-stair-climber","tag-stair-climber-exercise","tag-stair-climber-workout","tag-stair-climbing","tag-stair-climbing-for-weight-loss","tag-stair-exercises","tag-stair-formula-2r-t","tag-stair-steps","tag-staircase","tag-staircase-step","tag-stairs-and-staircase","tag-stairs-for-you","tag-stairs-workout","tag-step-2-climber","tag-step-climber","tag-step-stairs","tag-steps-for-stairs","tag-the-counter","tag-the-stairs","tag-three-stairs","tag-three-step-stairs","tag-trouble-climbing-stairs","tag-use-stairs","tag-what-is-staircase"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26213","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=26213"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26213\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26213"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26213"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26213"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}