{"id":2878,"date":"2021-10-23T18:15:00","date_gmt":"2021-10-23T12:45:00","guid":{"rendered":"https:\/\/www.interviewbit.com\/blog\/?p=2878"},"modified":"2022-06-15T11:53:30","modified_gmt":"2022-06-15T06:23:30","slug":"climbing-stairs-problem","status":"publish","type":"post","link":"https:\/\/www.interviewbit.com\/blog\/climbing-stairs-problem\/","title":{"rendered":"Climbing Stairs Problem"},"content":{"rendered":"\n<div class=\"gutentoc tocactive ullist\" style=\"max-width:400px\"><div class=\"gutentoc-toc-wrap\"><div class=\"gutentoc-toc-title-wrap\"><div class=\"gutentoc-toc-title\">Table Of Contents<\/div><div id=\"open\" class=\"toggletwo\">show<\/div><\/div><div id=\"toclist\"><div class=\"gutentoc-toc__list-wrap\"><ul class=\"gutentoc-toc__list\"><li><a href=\"#problem-statement\">Problem Statement<\/a><\/li><li><a href=\"#brute-force-recursive-approach\">Brute Force (Recursive) Approach<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-implementation-of-recursive-approach\">C++ Implementation of Recursive Approach<\/a><\/li><li><a href=\"#-java-implementation-of-recursive-approach\"> Java Implementation of Recursive Approach<\/a><\/li><li><a href=\"#python-implementation-of-recursive-approach\">Python Implementation of Recursive Approach<\/a><\/li><\/ul><li><a href=\"#bottom-up-approach\">Bottom-up Approach<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-implementation-of-dp-approach\">C++ Implementation of DP Approach<\/a><\/li><li><a href=\"#-java-implementation-of-dp-approach-\"> Java Implementation of DP Approach <\/a><\/li><li><a href=\"#-python-implementation-of-dp-approach-\"> Python Implementation of DP Approach <\/a><\/li><\/ul><li><a href=\"#fibonacci-number-approach\">Fibonacci Number Approach<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-implementation\">C++ Implementation<\/a><\/li><\/ul><li><a href=\"#practice-question\">Practice Question<\/a><\/li><li><a href=\"#-faqs\"> FAQs<\/a><\/li><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n<h2 id=\"problem-statement\">Problem Statement<\/h2>\n\n\n\n<p>Given a staircase of <strong>N<\/strong> steps and you can either climb 1 or 2 steps at a given time. The task is to return the count of distinct ways to climb to the top.<br><strong>Note: <\/strong>The order of the steps taken matters.<\/p>\n\n\n\n<p><strong>Examples:<\/strong><\/p>\n\n\n\n<p><strong>Input: <\/strong>N = 3<br><strong>Output: <\/strong>3<br><strong>Explanation:<\/strong><\/p>\n\n\n\n<p>There are three distinct ways of climbing a staircase of 3 steps :<\/p>\n\n\n\n[1, 1, 1], [2, 1] and [1, 2].<\/p>\n\n\n\n<figure class=\"wp-block-image size-full is-resized\"><img  loading=\"lazy\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"\"  class=\"wp-image-3106 pk-lazyload\"  width=\"382\"  height=\"404\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 382px) 100vw, 382px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image2-1.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image2-1.png 689w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image2-1-284x300.png 284w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image2-1-380x402.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image2-1-550x582.png 550w\" ><\/figure>\n\n\n\n<p><strong>Input: <\/strong>&nbsp;N = 2<br><strong>Output:<\/strong> 2<br><strong>Explanation:<\/strong><\/p>\n\n\n\n<p>There are two distinct ways of climbing a staircase of 3 steps :<\/p>\n\n\n\n[1, 1] and [2].<\/p>\n\n\n\n<hr class=\"wp-block-separator is-style-wide\"\/>\n\n\n\n<h2 class=\"is-style-default\" id=\"brute-force-recursive-approach\">Brute Force (Recursive) Approach<\/h2>\n\n\n\n<p>The approach is to consider all possible combination steps i.e. 1 and 2, at every step. To reach the <strong>Nth<\/strong> stair, one can jump from either (<strong>N &#8211; 1)th <\/strong>or from<strong> (N &#8211; 2)th <\/strong>stair. Hence, for each step, total ways would be the summation of (<strong>N &#8211; 1)th stair + (N &#8211; 2)<\/strong>th stair.<\/p>\n\n\n\n<p>The recursive function would be:<\/p>\n\n\n\n<p><strong>ClimbStairs(N) = ClimbStairs(N &#8211; 1) + ClimbStairs(N &#8211; 2)<\/strong>.<\/p>\n\n\n\n<p>If we observe carefully, the expression is nothing but the <strong>Fibonacci Sequence<\/strong>.<\/p>\n\n\n\n<p>SampleRecursive Tree for <strong>N = 5<\/strong>:<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img  loading=\"lazy\"  width=\"891\"  height=\"580\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"\"  class=\"wp-image-3109 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 891px) 100vw, 891px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image3-1.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image3-1.png 891w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image3-1-300x195.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image3-1-768x500.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image3-1-230x150.png 230w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image3-1-260x170.png 260w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image3-1-380x247.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image3-1-550x358.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image3-1-800x521.png 800w\" ><\/figure>\n\n\n\n<p><strong>Algorithm:<\/strong><\/p>\n\n\n\n<ul><li>If <strong>N &lt; 2, <\/strong>return <strong>1<\/strong>. This is the termination condition for the function.<\/li><li>Else, find the summation of <strong>ClimbStairs(N &#8211; 1) + ClimbStairs(N &#8211; 2)<\/strong>.<\/li><\/ul>\n\n\n\n<h3 id=\"c-implementation-of-recursive-approach\">C++ Implementation of Recursive Approach<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">int climbStairs(int N)\n{\n    if ( N &lt; 2 )\n        return 1;\n    else\n        return climbStairs(N-1) + climbStairs(N-2);\n}<\/pre>\n\n\n\n<h3 id=\"-java-implementation-of-recursive-approach\"><span id=\"java-implementation-of-recursive-approach\"> Java Implementation of Recursive Approach<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\"> static int climbStairs(int N){\n    if ( N &lt; 2 )\n        return 1;\n    else\n        return climbStairs(N-1) + climbStairs(N-2);\n}<\/pre>\n\n\n\n<h3 id=\"python-implementation-of-recursive-approach\">Python Implementation of Recursive Approach<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def climbStairs(N):\n    if N &lt; 2 :\n        return 1\n    else:\n        return climbStairs(N-1) + climbStairs(N-2)<\/pre>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"bottom-up-approach\">Bottom-up Approach<\/h2>\n\n\n\n<p>In the above approach, observe the recursion tree. It can be clearly seen that some of the subproblems are repeating. Hence, it is unnecessary to calculate those again and again. Therefore, we can store the result of those subproblems and retrieve the solution of those in O(1) time.<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img  loading=\"lazy\"  width=\"891\"  height=\"580\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"\"  class=\"wp-image-3110 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 891px) 100vw, 891px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image1-2.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image1-2.png 891w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image1-2-300x195.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image1-2-768x500.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image1-2-230x150.png 230w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image1-2-260x170.png 260w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image1-2-380x247.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image1-2-550x358.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image1-2-800x521.png 800w\" ><\/figure>\n\n\n\n<p>Since the problem contains an optimal substructure and has overlapping subproblems, it can be solved using <strong><a href=\"https:\/\/www.interviewbit.com\/courses\/programming\/dynamic-programming\/\" target=\"_blank\" rel=\"noreferrer noopener\">dynamic programming<\/a><\/strong>.<\/p>\n\n\n\n<p>One can reach the <strong>ith<\/strong> step in one of the two ways :<\/p>\n\n\n\n<ol><li>Take one step from <strong>(i &#8211; 1)th step.<\/strong><\/li><li>Take two steps from <strong>(i &#8211; 2)th step.<\/strong><\/li><\/ol>\n\n\n\n<p><strong>Algorithm<\/strong><\/p>\n\n\n\n<ul><li>Initialise a <strong>dp[] <\/strong>array of size <strong>N + 1<\/strong>.<\/li><li>Assign <strong>dp[0] <\/strong>and<strong> dp[1] <\/strong>to 1.<\/li><li>Iterate a loop from <strong>2<\/strong> till <strong>N<\/strong> and for each iteration:<ul><li><strong>dp[i] = dp[i &#8211; 1] + dp[i &#8211; 2]<\/strong><\/li><\/ul><\/li><li>Return the value of <strong>dp[N]<\/strong>.<\/li><\/ul>\n\n\n\n<h3 id=\"c-implementation-of-dp-approach\">C++ Implementation of DP Approach<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">int climbStairs(int N)\n{\n    int dp[N+1];\n    dp[0] = 1\n    dp[1] = 1\n    for (i = 2; i &lt;= N; i++){\n        dp[i] = dp[i-1] + dp[i-2];\n    }\n    return dp[N];\n}<\/pre>\n\n\n\n<h3 id=\"-java-implementation-of-dp-approach-\"><span id=\"java-implementation-of-dp-approach\"> Java Implementation of DP Approach <\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\"> static int climbStairs(int N)\n{\n    int dp[] = new int[N+1];\n    dp[0] = 1\n    dp[1] = 1\n    for (i = 2; i &lt;= N; i++){\n        dp[i] = dp[i-1] + dp[i-2];\n    }\n    return dp[N];\n}<\/pre>\n\n\n\n<h3 id=\"-python-implementation-of-dp-approach-\"><span id=\"python-implementation-of-dp-approach\"> Python Implementation of DP Approach <\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def climbStairs(N):\n    dp = [0]*(N + 1)\n    dp[0] = 1\n    dp[1] = 1\n        \n    for i in range(2, N + 1):\n        dp[i] = dp[i - 1] + dp[i - 2]\n            \n    return dp[N]<\/pre>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"fibonacci-number-approach\">Fibonacci Number Approach<\/h2>\n\n\n\n<p>In the above approach, the <strong>dp<\/strong> array is just storing the value of the previous two steps from the current <strong>ith<\/strong> position i.e. <strong>(i &#8211; 1)th <\/strong>and <strong>(i &#8211; 2)th <\/strong>position.<\/p>\n\n\n\n<p>The space complexity can be further optimized, since we just have to find an <strong>Nth<\/strong> number of the Fibonacci series having 1 and 2 as their first and second term respectively, i.e. <strong>Fib(1) = 1 and Fib(2) = 2<\/strong>.<\/p>\n\n\n\n<p><strong>Algorithm<\/strong><\/p>\n\n\n\n<ul><li>Initialise two variables <strong>first = 1<\/strong> and <strong>second = 2<\/strong>.<\/li><li>Iterate a loop from <strong>i = 3<\/strong> till <strong>i = N<\/strong> and for each step:<ul><li>Initialise a variable <strong>third = first + second<\/strong><\/li><li><strong>first = second<\/strong><\/li><li><strong>second = third<\/strong><\/li><\/ul><\/li><li>Return <strong>second<\/strong> after the iteration ends.<\/li><\/ul>\n\n\n\n<h3 id=\"c-implementation\">C++ Implementation<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">int climbStairs(int N)\n{\n    if (N == 1) {\n            return 1;\n    }\n    int first = 1;\n    int second = 2;\n    for (int i = 3; i &lt;= N; i++) {\n        int third = first + second;\n        first = second;\n        second = third;\n    }\n    return second;\n}<\/pre>\n\n\n\n<h4 id=\"java-implementati-on-\"><span id=\"java-implementation\">Java Implementati<strong>on<\/strong><\/span><\/h4>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\"> public int climbStairs(int N) {\n        if (N == 1) {\n            return 1;\n        }\n        int first = 1;\n        int second = 2;\n        for (int i = 3; i &lt;= N; i++) {\n            int third = first + second;\n            first = second;\n            second = third;\n        }\n        return second;\n    }<\/pre>\n\n\n\n<h4 id=\"-python-implementation\"><span id=\"python-implementation\"> Python Implementation<\/span><\/h4>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def climbStairs(N):\n    if N == 1:\n       return 1\n    first = 1;\n    second = 2;\n    for i in range(3, N + 1):\n        third = first + second;\n        first = second;\n        second = third;\n \n    return second;<\/pre>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"practice-question\">Practice Question<\/h2>\n\n\n\n<p><a href=\"https:\/\/www.interviewbit.com\/problems\/stairs\/\" target=\"_blank\" rel=\"noreferrer noopener\">Stairs Problem<\/a><\/p>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"-faqs\"><span id=\"faqs\"> FAQs<\/span><\/h2>\n\n\n\n<p><strong>What is the most efficient approach to solving<\/strong> the Climbing stairs problem? The approach to finding the Nth Fibonacci number is the most efficient approach since its time complexity is O(N) and space complexity is O(1).<\/p>\n\n\n\n<p><strong>How to solve this problem if it&#8217;s given that one<\/strong> can climb up to<strong> K steps at a time?<br><\/strong>If one can climb <strong>K<\/strong> steps at a time, try to find all possible combinations from each step from <strong>1<\/strong> to <strong>K. <\/strong>The recursive function would be :<br><strong>climbStairs(N, K) = climbStairs(N &#8211; 1, K) + climbStairs(N &#8211; 2, K) + \u2026 + climbStairs(N &#8211; K , K).<\/strong><\/p>\n","protected":false},"excerpt":{"rendered":"Problem Statement Given a staircase of N steps and you can either climb 1 or 2 steps at&hellip;\n","protected":false},"author":5,"featured_media":3146,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_daextam_enable_autolinks":"1","csco_singular_sidebar":"","csco_page_header_type":"","csco_appearance_grid":"","csco_page_load_nextpost":"","csco_post_video_location":[],"csco_post_video_location_hash":"","csco_post_video_url":"","csco_post_video_bg_start_time":0,"csco_post_video_bg_end_time":0},"categories":[145],"tags":[457,484,399],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2878"}],"collection":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/users\/5"}],"replies":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/comments?post=2878"}],"version-history":[{"count":6,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2878\/revisions"}],"predecessor-version":[{"id":9824,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2878\/revisions\/9824"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/3146"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=2878"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=2878"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=2878"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}