{"id":782,"date":"2025-07-24T17:12:26","date_gmt":"2025-07-24T11:42:26","guid":{"rendered":"https:\/\/codeanddebug.in\/blog\/?p=782"},"modified":"2025-07-24T17:12:45","modified_gmt":"2025-07-24T11:42:45","slug":"climbing-stairs-leetcode-70","status":"publish","type":"post","link":"https:\/\/codeanddebug.in\/blog\/climbing-stairs-leetcode-70\/","title":{"rendered":"Climbing Stairs | Leetcode 70 | Solved using Dynamic Programming"},"content":{"rendered":"\n<p>You are climbing a staircase with\u00a0<code>n<\/code>\u00a0steps. It takes\u00a0<code>n<\/code>\u00a0steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?<\/p>\n\n\n\n<p>Here&#8217;s the [<strong><a href=\"https:\/\/leetcode.com\/problems\/climbing-stairs\/description\/\" target=\"_blank\" rel=\"noreferrer noopener\"><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-vivid-purple-color\"><span style=\"text-decoration: underline;\">Problem Link<\/span><\/mark><\/a><\/strong>] to begin with.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted\"><strong>Input:<\/strong> n = 2<br><strong>Output:<\/strong> 2<br><strong>Explanation:<\/strong> There are two ways to climb to the top.<br>1. 1 step + 1 step<br>2. 2 steps<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted\"><strong>Input:<\/strong> n = 3<br><strong>Output:<\/strong> 3<br><strong>Explanation:<\/strong> There are three ways to climb to the top.<br>1. 1 step + 1 step + 1 step<br>2. 1 step + 2 steps<br>3. 2 steps + 1 step<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><code>1 &lt;= n &lt;= 45<\/code><\/li>\n<\/ul>\n\n\n<div style=\"max-width: -moz-fit-content; \" class=\"wp-block-ub-table-of-contents-block ub_table-of-contents ub_table-of-contents-collapsed\" id=\"ub_table-of-contents-fbf18626-3ccd-466e-aa19-9d448a45205d\" data-linktodivider=\"false\" data-showtext=\"show\" data-hidetext=\"hide\" data-scrolltype=\"auto\" data-enablesmoothscroll=\"true\" data-initiallyhideonmobile=\"true\" data-initiallyshow=\"false\"><div class=\"ub_table-of-contents-header-container\" style=\"\">\n\t\t\t<div class=\"ub_table-of-contents-header\" style=\"text-align: left; \">\n\t\t\t\t<div class=\"ub_table-of-contents-title\">Contents:<\/div>\n\t\t\t\t<div class=\"ub_table-of-contents-header-toggle\">\n\t\t\t<div class=\"ub_table-of-contents-toggle\" style=\"\">\n\t\t\t\u00a0[<a class=\"ub_table-of-contents-toggle-link\" href=\"#\" style=\"\">show<\/a>]\n\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t<\/div>\n\t\t<\/div><div class=\"ub_table-of-contents-extra-container\" style=\"\">\n\t\t\t<div class=\"ub_table-of-contents-container ub_table-of-contents-1-column ub-hide\">\n\t\t\t\t<ul style=\"\"><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/climbing-stairs-leetcode-70\/#0-solution-1-brute-force-approach-pure-recursion\" style=\"\">Solution 1: Brute Force Approach (Pure Recursion)<\/a><ul><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/climbing-stairs-leetcode-70\/#1-intuition\" style=\"\">Intuition<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/climbing-stairs-leetcode-70\/#2-detailed-approach\" style=\"\">Detailed Approach<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/climbing-stairs-leetcode-70\/#3-code\" style=\"\">Code<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/climbing-stairs-leetcode-70\/#4-code-explanation\" style=\"\">Code Explanation<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/climbing-stairs-leetcode-70\/#5-dry-run\" style=\"\">Dry Run<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/climbing-stairs-leetcode-70\/#6-time-and-space-complexity\" style=\"\">Time and Space Complexity<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/climbing-stairs-leetcode-70\/#7-simplifying-it\" style=\"\">Simplifying It<\/a><\/li><\/ul><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/climbing-stairs-leetcode-70\/#8-solution-2-memoization-approach-top-down-dynamic-programming\" style=\"\">Solution 2: Memoization Approach (Top-Down Dynamic Programming)<\/a><ul><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/climbing-stairs-leetcode-70\/#9-intuition\" style=\"\">Intuition<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/climbing-stairs-leetcode-70\/#10-detailed-approach\" style=\"\">Detailed Approach<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/climbing-stairs-leetcode-70\/#11-code\" style=\"\">Code<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/climbing-stairs-leetcode-70\/#12-code-explanation\" style=\"\">Code Explanation<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/climbing-stairs-leetcode-70\/#13-dry-run\" style=\"\">Dry Run<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/climbing-stairs-leetcode-70\/#14-time-and-space-complexity\" style=\"\">Time and Space Complexity<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/climbing-stairs-leetcode-70\/#15-simplifying-it\" style=\"\">Simplifying It<\/a><\/li><\/ul><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/climbing-stairs-leetcode-70\/#16-solution-3-tabulation-approach-bottom-up-dynamic-programming\" style=\"\">Solution 3: Tabulation Approach (Bottom-Up Dynamic Programming)<\/a><ul><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/climbing-stairs-leetcode-70\/#17-intuition\" style=\"\">Intuition<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/climbing-stairs-leetcode-70\/#18-detailed-approach\" style=\"\">Detailed Approach<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/climbing-stairs-leetcode-70\/#19-code\" style=\"\">Code<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/climbing-stairs-leetcode-70\/#20-code-explanation\" style=\"\">Code Explanation<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/climbing-stairs-leetcode-70\/#21-dry-run\" style=\"\">Dry Run<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/climbing-stairs-leetcode-70\/#22-time-and-space-complexity\" style=\"\">Time and Space Complexity<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/climbing-stairs-leetcode-70\/#23-simplifying-it\" style=\"\">Simplifying It<\/a><\/li><\/ul><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/climbing-stairs-leetcode-70\/#24-solution-4-space-optimized-tabulation-optimal-approach\" style=\"\">Solution 4: Space-Optimized Tabulation (Optimal Approach)<\/a><ul><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/climbing-stairs-leetcode-70\/#25-intuition\" style=\"\">Intuition<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/climbing-stairs-leetcode-70\/#26-detailed-approach\" style=\"\">Detailed Approach<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/climbing-stairs-leetcode-70\/#27-code\" style=\"\">Code<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/climbing-stairs-leetcode-70\/#28-code-explanation\" style=\"\">Code Explanation<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/climbing-stairs-leetcode-70\/#29-dry-run\" style=\"\">Dry Run<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/climbing-stairs-leetcode-70\/#30-time-and-space-complexity\" style=\"\">Time and Space Complexity<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/climbing-stairs-leetcode-70\/#31-simplifying-it\" style=\"\">Simplifying It<\/a><\/li><\/ul><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/climbing-stairs-leetcode-70\/#32-summary\" style=\"\">Summary<\/a><\/li><\/ul>\n\t\t\t<\/div>\n\t\t<\/div><\/div>\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"0-solution-1-brute-force-approach-pure-recursion\">Solution 1: Brute Force Approach (Pure Recursion)<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"1-intuition\">Intuition<\/h3>\n\n\n\n<p>Think of this like deciding at every step whether to take a small jump (1 step) or a big jump (2 steps)! The most natural way to solve this is to recursively explore all possible combinations of 1-step and 2-step climbs. For the current position at stair&nbsp;<code>index<\/code>, the number of ways to reach the top is the sum of ways from taking 1 step (to index-1) plus ways from taking 2 steps (to index-2). It&#8217;s like asking &#8220;From here, how many ways if I take 1 step? How many if I take 2 steps?&#8221; and adding them up. This continues until you reach the bottom (0 or 1 stair left, which have obvious solutions).<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"2-detailed-approach\">Detailed Approach<\/h3>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Base Cases<\/strong>: If index == 0 (no stairs left), there&#8217;s 1 way (do nothing). If index == 1, there&#8217;s 1 way (take one step).<\/li>\n\n\n\n<li><strong>Recursive Case<\/strong>: For index \u2265 2, return func(index-1) + func(index-2).<\/li>\n\n\n\n<li><strong>Direct Implementation<\/strong>: Translate the decision process directly into recursive code.<\/li>\n\n\n\n<li><strong>No Optimization<\/strong>: Make fresh recursive calls every time, even for overlapping subproblems.<\/li>\n\n\n\n<li><strong>Tree Structure<\/strong>: Creates a binary tree of recursive calls with lots of redundancy (e.g., func(2) calculated multiple times).<\/li>\n<\/ol>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"3-code\">Code<\/h3>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro cbp-has-line-numbers\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;--cbp-line-number-color:#D4D4D4;--cbp-line-number-width:calc(2 * 0.6 * .875rem);line-height:1.5rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"class Solution:\n    def func(self, index):\n        # Base cases: 1 way for 0 or 1 stair\n        if index == 0 or index == 1:\n            return 1\n        \n        # Recursive case: ways = ways from (index-1) + ways from (index-2)\n        return self.func(index - 1) + self.func(index - 2)\n\n    def climbStairs(self, n: int) -&gt; int:\n        return self.func(n)\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #569CD6\">class<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #4EC9B0\">Solution<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">func<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">index<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Base cases: 1 way for 0 or 1 stair<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> index == <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">or<\/span><span style=\"color: #D4D4D4\"> index == <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #B5CEA8\">1<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Recursive case: ways = ways from (index-1) + ways from (index-2)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.func(index - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">) + <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.func(index - <\/span><span style=\"color: #B5CEA8\">2<\/span><span style=\"color: #D4D4D4\">)<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">climbStairs<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">n<\/span><span style=\"color: #D4D4D4\">: <\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">) -&gt; <\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.func(n)<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"4-code-explanation\">Code Explanation<\/h3>\n\n\n\n<p>This solution directly models the climbing choices with recursion. The&nbsp;<code>func<\/code>&nbsp;handles base cases where 0 stairs have 1 way (you&#8217;re already at the top) and 1 stair has 1 way (must take one step). For any other index, it recursively calculates the ways by considering a 1-step climb (func(index-1)) and a 2-step climb (func(index-2)), then adds them. The main function&nbsp;<code>climbStairs<\/code>&nbsp;starts the recursion from n. This creates a binary tree of calls, where each node represents a decision point.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"5-dry-run\">Dry Run<\/h3>\n\n\n\n<p>Let&#8217;s trace through:&nbsp;<code>n = 4<\/code><\/p>\n\n\n\n<p><strong>func(4):<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Not 0 or 1, so return func(3) + func(2)<\/li>\n<\/ul>\n\n\n\n<p><strong>func(3):<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Not 0 or 1, so return func(2) + func(1)<br><strong>func(2):<\/strong>\n<ul class=\"wp-block-list\">\n<li>Not 0 or 1, so return func(1) + func(0)<br><strong>func(1):<\/strong>&nbsp;==1, return 1<br><strong>func(0):<\/strong>&nbsp;==0, return 1<\/li>\n\n\n\n<li>func(2) = 1 + 1 = 2<br><strong>func(1):<\/strong>&nbsp;==1, return 1<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>func(3) = 2 + 1 = 3<\/li>\n<\/ul>\n\n\n\n<p><strong>func(2):<\/strong>&nbsp;(calculated again!)<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Not 0 or 1, so return func(1) + func(0)<br><strong>func(1):<\/strong>&nbsp;==1, return 1<br><strong>func(0):<\/strong>&nbsp;==0, return 1<\/li>\n\n\n\n<li>func(2) = 1 + 1 = 2<\/li>\n<\/ul>\n\n\n\n<p><strong>Final:<\/strong>&nbsp;func(4) = 3 + 2 = 5<\/p>\n\n\n\n<p><strong>Notice:<\/strong>&nbsp;func(2), func(1), func(0) are recalculated multiple times!<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"6-time-and-space-complexity\">Time and Space Complexity<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Time Complexity:<\/strong>&nbsp;O(2^n) &#8211; Each call branches into 2 more calls, leading to exponential growth<\/li>\n\n\n\n<li><strong>Space Complexity:<\/strong>&nbsp;O(n) &#8211; Maximum depth of recursion stack equals n<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"7-simplifying-it\">Simplifying It<\/h3>\n\n\n\n<p>This approach is like exploring every possible path up the stairs by actually walking them all, but forgetting paths you&#8217;ve already walked, so you end up walking the same lower sections of stairs over and over again! Very intuitive but extremely inefficient for large n.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"8-solution-2-memoization-approach-top-down-dynamic-programming\">Solution 2: Memoization Approach (Top-Down Dynamic Programming)<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"9-intuition\">Intuition<\/h3>\n\n\n\n<p>What if we remembered the number of ways to climb each subsection of stairs so we don&#8217;t have to recalculate them? Memoization adds a &#8220;memory&#8221; layer to our recursive approach by storing the results of subproblems in an array. When we need the ways for a particular index, we first check if we&#8217;ve already computed it &#8211; if yes, just return the stored value. It&#8217;s like having a notebook where you write down &#8220;Number of ways from stair 3: 3&#8221; and look it up next time instead of re-exploring.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"10-detailed-approach\">Detailed Approach<\/h3>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Create Memoization Array<\/strong>: Initialize dp array of size n+1 with -1 (uncomputed).<\/li>\n\n\n\n<li><strong>Check Cache First<\/strong>: In func, if dp[index] != -1, return cached value.<\/li>\n\n\n\n<li><strong>Compute and Store<\/strong>: If not cached, compute recursively and store in dp[index].<\/li>\n\n\n\n<li><strong>Same Recursive Structure<\/strong>: Maintain the choice-based recursion but add caching.<\/li>\n\n\n\n<li><strong>One-Time Computation<\/strong>: Each subproblem (ways for each index) is solved exactly once.<\/li>\n<\/ol>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"11-code\">Code<\/h3>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro cbp-has-line-numbers\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;--cbp-line-number-color:#D4D4D4;--cbp-line-number-width:calc(2 * 0.6 * .875rem);line-height:1.5rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"class Solution:\n    def func(self, index, dp):\n        # Base cases: 1 way for 0 or 1 stair\n        if index == 0 or index == 1:\n            return 1\n        \n        # Check if already computed\n        if dp[index] != -1:\n            return dp[index]  # Return cached result\n        \n        # Compute and store\n        dp[index] = self.func(index - 1, dp) + self.func(index - 2, dp)\n        return dp[index]\n\n    def climbStairs(self, n: int) -&gt; int:\n        # Initialize memoization array\n        dp = [-1] * (n + 1)\n        return self.func(n, dp)\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #569CD6\">class<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #4EC9B0\">Solution<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">func<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">index<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">dp<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Base cases: 1 way for 0 or 1 stair<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> index == <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">or<\/span><span style=\"color: #D4D4D4\"> index == <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #B5CEA8\">1<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Check if already computed<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> dp[index] != -<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> dp[index]  <\/span><span style=\"color: #6A9955\"># Return cached result<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Compute and store<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        dp[index] = <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.func(index - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, dp) + <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.func(index - <\/span><span style=\"color: #B5CEA8\">2<\/span><span style=\"color: #D4D4D4\">, dp)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> dp[index]<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">climbStairs<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">n<\/span><span style=\"color: #D4D4D4\">: <\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">) -&gt; <\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Initialize memoization array<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        dp = [-<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">] * (n + <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.func(n, dp)<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"12-code-explanation\">Code Explanation<\/h3>\n\n\n\n<p>This solution enhances the recursive approach with memoization. The&nbsp;<code>dp<\/code>&nbsp;array serves as our cache, starting with -1 for uncomputed states. Before recursing, we check if&nbsp;<code>dp[index] != -1<\/code>&nbsp;&#8211; if true, return the stored ways immediately. If not, compute by recursing on index-1 and index-2, store the sum in&nbsp;<code>dp[index]<\/code>, and return it. This turns exponential time into linear by ensuring each index&#8217;s ways are calculated once and reused.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"13-dry-run\">Dry Run<\/h3>\n\n\n\n<p>Let&#8217;s trace through:&nbsp;<code>n = 4<\/code><\/p>\n\n\n\n<p><strong>Initial: dp = [-1, -1, -1, -1, -1]<\/strong><\/p>\n\n\n\n<p><strong>func(4, dp):<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>index=4 &gt;1 and dp=-1, so compute<\/li>\n\n\n\n<li>dp = func(3, dp) + func(2, dp)<\/li>\n<\/ul>\n\n\n\n<p><strong>func(3, dp):<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>index=3 &gt;1 and dp=-1, so compute<\/li>\n\n\n\n<li>dp = func(2, dp) + func(1, dp)<\/li>\n<\/ul>\n\n\n\n<p><strong>func(2, dp):<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>index=2 &gt;1 and dp=-1, so compute<\/li>\n\n\n\n<li>dp = func(1, dp) + func(0, dp)<br><strong>func(1, dp):<\/strong>&nbsp;==1, return 1<br><strong>func(0, dp):<\/strong>&nbsp;==0, return 1<\/li>\n\n\n\n<li>dp = 1 + 1 = 2,&nbsp;<strong>dp = [-1, -1, 2, -1, -1]<\/strong><\/li>\n<\/ul>\n\n\n\n<p><strong>func(1, dp):<\/strong>&nbsp;==1, return 1<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>dp = 2 + 1 = 3,&nbsp;<strong>dp = [-1, -1, 2, 3, -1]<\/strong><\/li>\n<\/ul>\n\n\n\n<p><strong>func(2, dp):<\/strong>&nbsp;(called again from func(4))<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>dp = 2 != -1,&nbsp;<strong>return cached 2<\/strong>&nbsp;(no recompute!)<\/li>\n<\/ul>\n\n\n\n<p><strong>Final:<\/strong>&nbsp;dp = 3 + 2 = 5,&nbsp;<strong>dp = [-1, -1, 2, 3, 5]<\/strong><\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"14-time-and-space-complexity\">Time and Space Complexity<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Time Complexity:<\/strong>&nbsp;O(n) &#8211; Each index from 0 to n is computed exactly once<\/li>\n\n\n\n<li><strong>Space Complexity:<\/strong>&nbsp;O(n) &#8211; dp array of size n+1 plus O(n) recursion stack<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"15-simplifying-it\">Simplifying It<\/h3>\n\n\n\n<p>This approach is like exploring the stairs but keeping a notebook of &#8220;ways from here&#8221; at each landing. The first time you figure out the ways from stair 3, you note it down. Next time you reach stair 3 from another path, you just read your note instead of re-exploring!<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"16-solution-3-tabulation-approach-bottom-up-dynamic-programming\">Solution 3: Tabulation Approach (Bottom-Up Dynamic Programming)<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"17-intuition\">Intuition<\/h3>\n\n\n\n<p>Instead of starting from the top of the stairs and working down, let&#8217;s start from the bottom and build up! Tabulation fills an array from the base cases (0 and 1 stair) upwards to n, where the ways to reach each stair i is the sum of ways to reach i-1 and i-2. It&#8217;s like counting the ways step by step, building on what you already know from lower stairs.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"18-detailed-approach\">Detailed Approach<\/h3>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Initialize DP Array<\/strong>: Create dp of size n+1, set dp = 1, dp<a href=\"https:\/\/leetcode.com\/problems\/climbing-stairs\/description\/\" target=\"_blank\" rel=\"noreferrer noopener\"><\/a>&nbsp;= 1.<\/li>\n\n\n\n<li><strong>Bottom-Up Filling<\/strong>: For index from 2 to n, dp[index] = dp[index-1] + dp[index-2].<\/li>\n\n\n\n<li><strong>Sequential Order<\/strong>: Ensure dependencies (lower indices) are computed first.<\/li>\n\n\n\n<li><strong>No Recursion<\/strong>: Pure loop-based approach avoids stack overhead.<\/li>\n\n\n\n<li><strong>Direct Access<\/strong>: Final answer is simply dp[n].<\/li>\n<\/ol>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"19-code\">Code<\/h3>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro cbp-has-line-numbers\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;--cbp-line-number-color:#D4D4D4;--cbp-line-number-width:calc(2 * 0.6 * .875rem);line-height:1.5rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"class Solution:\n    def climbStairs(self, n: int) -&gt; int:\n        # Initialize DP array\n        dp = [-1] * (n + 1)\n        dp[0] = 1  # 1 way for 0 stairs\n        dp[1] = 1  # 1 way for 1 stair\n        \n        # Fill array bottom-up\n        for index in range(2, n + 1):\n            dp[index] = dp[index - 1] + dp[index - 2]  # Ways = from (index-1) + from (index-2)\n        \n        return dp[n]\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #569CD6\">class<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #4EC9B0\">Solution<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">climbStairs<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">n<\/span><span style=\"color: #D4D4D4\">: <\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">) -&gt; <\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Initialize DP array<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        dp = [-<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">] * (n + <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        dp[<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">] = <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">  <\/span><span style=\"color: #6A9955\"># 1 way for 0 stairs<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        dp[<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">] = <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">  <\/span><span style=\"color: #6A9955\"># 1 way for 1 stair<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Fill array bottom-up<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> index <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #B5CEA8\">2<\/span><span style=\"color: #D4D4D4\">, n + <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            dp[index] = dp[index - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">] + dp[index - <\/span><span style=\"color: #B5CEA8\">2<\/span><span style=\"color: #D4D4D4\">]  <\/span><span style=\"color: #6A9955\"># Ways = from (index-1) + from (index-2)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> dp[n]<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"20-code-explanation\">Code Explanation<\/h3>\n\n\n\n<p>This solution uses iteration to build the solution from base cases up. We set dp = 1 (one way to stay at ground) and dp<a rel=\"noreferrer noopener\" target=\"_blank\" href=\"https:\/\/leetcode.com\/problems\/climbing-stairs\/description\/\"><\/a>&nbsp;= 1 (one way to climb one stair). The loop computes each dp[index] using the previously filled values, modeling the choice of coming from 1 step below or 2 steps below. This eliminates recursion and directly computes the answer in linear time.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"21-dry-run\">Dry Run<\/h3>\n\n\n\n<p>Let&#8217;s trace through:&nbsp;<code>n = 5<\/code><\/p>\n\n\n\n<p><strong>Initial: dp = [1, 1, ?, ?, ?, ?]<\/strong><\/p>\n\n\n\n<p><strong>index = 2:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>dp = dp<a href=\"https:\/\/leetcode.com\/problems\/climbing-stairs\/description\/\" target=\"_blank\" rel=\"noreferrer noopener\"><\/a>&nbsp;+ dp = 1 + 1 = 2<\/li>\n\n\n\n<li><strong>dp = [1, 1, 2, ?, ?, ?]<\/strong><\/li>\n<\/ul>\n\n\n\n<p><strong>index = 3:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>dp = dp + dp<a href=\"https:\/\/leetcode.com\/problems\/climbing-stairs\/description\/\" target=\"_blank\" rel=\"noreferrer noopener\"><\/a>&nbsp;= 2 + 1 = 3<\/li>\n\n\n\n<li><strong>dp = [1, 1, 2, 3, ?, ?]<\/strong><\/li>\n<\/ul>\n\n\n\n<p><strong>index = 4:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>dp = dp + dp = 3 + 2 = 5<\/li>\n\n\n\n<li><strong>dp = [1, 1, 2, 3, 5, ?]<\/strong><\/li>\n<\/ul>\n\n\n\n<p><strong>index = 5:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>dp = dp + dp = 5 + 3 = 8<\/li>\n\n\n\n<li>**dp = [1, 1, 2,<br><strong>Return dp = 8<\/strong><\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"22-time-and-space-complexity\">Time and Space Complexity<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Time Complexity:<\/strong>&nbsp;O(n) &#8211; Single loop from 2 to n, O(1) per iteration<\/li>\n\n\n\n<li><strong>Space Complexity:<\/strong>&nbsp;O(n) &#8211; dp array of size n+1<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"23-simplifying-it\">Simplifying It<\/h3>\n\n\n\n<p>This approach is like building a map of the stairs where you note the number of ways to reach each landing, starting from the ground floor. For each higher landing, you just add the ways from the landing directly below and two below &#8211; very organized!<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"24-solution-4-space-optimized-tabulation-optimal-approach\">Solution 4: Space-Optimized Tabulation (Optimal Approach)<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"25-intuition\">Intuition<\/h3>\n\n\n\n<p>Do we really need to store ways for ALL stairs from 0 to n? No &#8211; to compute ways for the next stair, we only need the ways for the previous two! Use two variables to track these, updating them as we &#8220;climb.&#8221; It&#8217;s like only remembering the ways to the last two landings you&#8217;ve reached.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"26-detailed-approach\">Detailed Approach<\/h3>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Initialize Variables<\/strong>: prev2 = 1 (ways for 0), prev = 1 (ways for 1).<\/li>\n\n\n\n<li><strong>Sliding Window<\/strong>: For each from 2 to n, curr = prev + prev2.<\/li>\n\n\n\n<li><strong>Update<\/strong>: prev2 = prev, prev = curr (slide the window up).<\/li>\n\n\n\n<li><strong>Constant Space<\/strong>: Only 3 variables needed.<\/li>\n\n\n\n<li><strong>Handle Small n<\/strong>: Implicitly covered, but loop starts from 2.<\/li>\n<\/ol>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"27-code\">Code<\/h3>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro cbp-has-line-numbers\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;--cbp-line-number-color:#D4D4D4;--cbp-line-number-width:calc(2 * 0.6 * .875rem);line-height:1.5rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"class Solution:\n    def climbStairs(self, n: int) -&gt; int:\n        # Base cases implicitly handled by initialization\n        if n &lt;= 1:\n            return 1\n        \n        # Initialize previous two ways\n        prev2 = 1  # Ways for 0 stairs\n        prev = 1   # Ways for 1 stair\n        \n        # Compute ways up to n\n        for _ in range(2, n + 1):\n            curr = prev + prev2  # Ways for current = prev + prev2\n            prev2 = prev         # Slide: prev2 becomes prev\n            prev = curr          # Slide: prev becomes curr\n        \n        return prev  # prev now holds ways for n\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #569CD6\">class<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #4EC9B0\">Solution<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">climbStairs<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">n<\/span><span style=\"color: #D4D4D4\">: <\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">) -&gt; <\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Base cases implicitly handled by initialization<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> n &lt;= <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #B5CEA8\">1<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Initialize previous two ways<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        prev2 = <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">  <\/span><span style=\"color: #6A9955\"># Ways for 0 stairs<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        prev = <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">   <\/span><span style=\"color: #6A9955\"># Ways for 1 stair<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Compute ways up to n<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> _ <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #B5CEA8\">2<\/span><span style=\"color: #D4D4D4\">, n + <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            curr = prev + prev2  <\/span><span style=\"color: #6A9955\"># Ways for current = prev + prev2<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            prev2 = prev         <\/span><span style=\"color: #6A9955\"># Slide: prev2 becomes prev<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            prev = curr          <\/span><span style=\"color: #6A9955\"># Slide: prev becomes curr<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> prev  <\/span><span style=\"color: #6A9955\"># prev now holds ways for n<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"28-code-explanation\">Code Explanation<\/h3>\n\n\n\n<p>This optimal solution tracks only the last two ways values. Start with prev2=1 (0 stairs) and prev=1 (1 stair). For each higher stair, compute curr as sum of prev and prev2, then update prev2 to prev and prev to curr. This maintains the two most recent ways values. After the loop, prev equals the ways for n. This achieves O(n) time with O(1) space.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"29-dry-run\">Dry Run<\/h3>\n\n\n\n<p>Let&#8217;s trace through:&nbsp;<code>n = 5<\/code><\/p>\n\n\n\n<p><strong>Initial: prev2 = 1 (0 stairs), prev = 1 (1 stair)<\/strong><\/p>\n\n\n\n<p><strong>i = 2:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>curr = prev + prev2 = 1 + 1 = 2 (2 stairs)<\/li>\n\n\n\n<li>prev2 = prev = 1, prev = curr = 2<\/li>\n\n\n\n<li><strong>State: prev2=1 (1 stair), prev=2 (2 stairs)<\/strong><\/li>\n<\/ul>\n\n\n\n<p><strong>i = 3:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>curr = prev + prev2 = 2 + 1 = 3 (3 stairs)<\/li>\n\n\n\n<li>prev2 = prev = 2, prev = curr = 3<\/li>\n\n\n\n<li><strong>State: prev2=2 (2 stairs), prev=3 (3 stairs)<\/strong><\/li>\n<\/ul>\n\n\n\n<p><strong>i = 4:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>curr = prev + prev2 = 3 + 2 = 5 (4 stairs)<\/li>\n\n\n\n<li>prev2 = prev = 3, prev = curr = 5<\/li>\n\n\n\n<li><strong>State: prev2=3 (3 stairs), prev=5 (4 stairs)<\/strong><\/li>\n<\/ul>\n\n\n\n<p><strong>i = 5:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>curr = prev + prev2 = 5 + 3 = 8 (5 stairs)<\/li>\n\n\n\n<li>prev2 = prev = 5, prev = curr = 8<\/li>\n\n\n\n<li><strong>State: prev2=5 (4 stairs), prev=8 (5 stairs)<\/strong><\/li>\n<\/ul>\n\n\n\n<p><strong>Return prev = 8<\/strong><\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"30-time-and-space-complexity\">Time and Space Complexity<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Time Complexity:<\/strong>&nbsp;O(n) &#8211; Single loop from 2 to n, O(1) per iteration<\/li>\n\n\n\n<li><strong>Space Complexity:<\/strong>&nbsp;O(1) &#8211; Only a few variables used<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"31-simplifying-it\">Simplifying It<\/h3>\n\n\n\n<p>This approach is like climbing the stairs while only remembering how many ways you could have reached the last two steps. As you take each new step, you update your memory with the new total, forgetting older info since you don&#8217;t need it anymore!<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"32-summary\">Summary<\/h2>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><thead><tr><th>Approach<\/th><th>Time<\/th><th>Space<\/th><th>Difficulty<\/th><th>Best For<\/th><\/tr><\/thead><tbody><tr><td>Recursion (Brute Force)<\/td><td>O(2^n)<\/td><td>O(n)<\/td><td>Easy<\/td><td>Understanding the concept<\/td><\/tr><tr><td>Memoization (Top-Down DP)<\/td><td>O(n)<\/td><td>O(n)<\/td><td>Medium<\/td><td>Learning DP concepts<\/td><\/tr><tr><td>Tabulation (Bottom-Up DP)<\/td><td>O(n)<\/td><td>O(n)<\/td><td>Medium<\/td><td>Systematic DP approach<\/td><\/tr><tr><td>Space-Optimized Tabulation<\/td><td>O(n)<\/td><td>O(1)<\/td><td>Medium-Hard<\/td><td>Production code<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>The&nbsp;<strong>space-optimized tabulation<\/strong>&nbsp;is the best for efficiency, with optimal time and minimal space. Each approach builds on the last, showing DP evolution: from wasteful recursion to cached recursion, to iterative building, to ultra-efficient variable tracking. Note that this problem is mathematically equivalent to the Fibonacci sequence, shifted by one index!<\/p>\n\n\n\n<div class=\"wp-block-buttons is-content-justification-center is-layout-flex wp-container-core-buttons-is-layout-16018d1d wp-block-buttons-is-layout-flex\">\n<div class=\"wp-block-button\"><a class=\"wp-block-button__link wp-element-button\" href=\"https:\/\/codeanddebug.in\/course\/zero-to-hero-python-dsa\" target=\"_blank\" rel=\"noreferrer noopener\">Join our Advance DSA COURSE<\/a><\/div>\n<\/div>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><em>For any changes to the article, kindly email at <a href=\"mailto:code@codeanddebug.in\" target=\"_blank\" rel=\"noreferrer noopener\">code@codeanddebug.in<\/a> or contact us at <a href=\"tel:+91-9712928220\" target=\"_blank\" rel=\"noreferrer noopener\">+91-9712928220<\/a>.<\/em><\/p>\n","protected":false},"excerpt":{"rendered":"<p>You are climbing a staircase with\u00a0n\u00a0steps. It takes\u00a0n\u00a0steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top? Here&#8217;s the [Problem Link] to begin with. Example 1: Input: n = 2Output: 2Explanation: There are two ways to climb to the<\/p>\n","protected":false},"author":1,"featured_media":784,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"ub_ctt_via":"","footnotes":""},"categories":[3,4],"tags":[36,8],"class_list":{"0":"post-782","1":"post","2":"type-post","3":"status-publish","4":"format-standard","5":"has-post-thumbnail","7":"category-data-structures-and-algorithm","8":"category-beginner","9":"tag-dynamic-programming","10":"tag-easy"},"featured_image_src":"https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/07\/climbing-stairs-featured-image.png","author_info":{"display_name":"codeanddebug","author_link":"https:\/\/codeanddebug.in\/blog\/author\/codeanddebug\/"},"_links":{"self":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/782","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/comments?post=782"}],"version-history":[{"count":4,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/782\/revisions"}],"predecessor-version":[{"id":790,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/782\/revisions\/790"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media\/784"}],"wp:attachment":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media?parent=782"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/categories?post=782"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/tags?post=782"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}