{"id":776,"date":"2025-07-24T15:37:29","date_gmt":"2025-07-24T10:07:29","guid":{"rendered":"https:\/\/codeanddebug.in\/blog\/?p=776"},"modified":"2025-07-24T15:37:31","modified_gmt":"2025-07-24T10:07:31","slug":"nth-fibonacci-number-introduction-to-dynamic-programming","status":"publish","type":"post","link":"https:\/\/codeanddebug.in\/blog\/nth-fibonacci-number-introduction-to-dynamic-programming\/","title":{"rendered":"Nth Fibonacci Number | Introduction to Dynamic Programming"},"content":{"rendered":"\n<p>Given a non-negative integer&nbsp;<strong>n<\/strong>, your task is to find the&nbsp;<strong>nth<\/strong>&nbsp;<strong>Fibonacci<\/strong>&nbsp;<strong>number<\/strong>.<\/p>\n\n\n\n<p>The&nbsp;<a href=\"https:\/\/www.geeksforgeeks.org\/fibonacci-series\/\" target=\"_blank\" rel=\"noreferrer noopener\">Fibonacci sequence<\/a>&nbsp;is a sequence where the next term is the sum of the previous two terms. The first two terms of the Fibonacci sequence are 0 followed by 1. The Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21.<\/p>\n\n\n\n<p>Here&#8217;s the [<strong><a href=\"https:\/\/www.geeksforgeeks.org\/problems\/nth-fibonacci-number1335\/1\" 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>The Fibonacci sequence is defined as follows:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>F(0) = 0<\/li>\n\n\n\n<li>F(1) = 1<\/li>\n\n\n\n<li>F(n) = F(n &#8211; 1) + F(n &#8211; 2) for n &gt; 1<\/li>\n<\/ul>\n\n\n\n<p><strong>Examples :<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted\"><strong>Input: <\/strong>n = 5\n<strong>Output: <\/strong>5\n<strong>Explanation<\/strong>: The 5th Fibonacci number is 5.<\/pre>\n\n\n\n<pre class=\"wp-block-preformatted\"><strong>Input<\/strong>: n = 0<br><strong>Output:<\/strong> 0&nbsp;<br><strong>Explanation<\/strong>: The 0th Fibonacci number is 0.<\/pre>\n\n\n\n<pre class=\"wp-block-preformatted\"><strong>Input: <\/strong>n = 1\n<strong>Output: <\/strong>1\n<strong>Explanation<\/strong>: The 1st Fibonacci number is 1.<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><br>0 \u2264 n \u2264 30<\/p>\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-81689355-c74c-4a73-8f1d-4e7583527f58\" 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\/nth-fibonacci-number-introduction-to-dynamic-programming\/#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\/nth-fibonacci-number-introduction-to-dynamic-programming\/#1-intuition\" style=\"\">Intuition<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/nth-fibonacci-number-introduction-to-dynamic-programming\/#2-detailed-approach\" style=\"\">Detailed Approach<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/nth-fibonacci-number-introduction-to-dynamic-programming\/#3-code\" style=\"\">Code<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/nth-fibonacci-number-introduction-to-dynamic-programming\/#4-code-explanation\" style=\"\">Code Explanation<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/nth-fibonacci-number-introduction-to-dynamic-programming\/#5-dry-run\" style=\"\">Dry Run<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/nth-fibonacci-number-introduction-to-dynamic-programming\/#6-time-and-space-complexity\" style=\"\">Time and Space Complexity<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/nth-fibonacci-number-introduction-to-dynamic-programming\/#7-simplifying-it\" style=\"\">Simplifying It<\/a><\/li><\/ul><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/nth-fibonacci-number-introduction-to-dynamic-programming\/#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\/nth-fibonacci-number-introduction-to-dynamic-programming\/#9-intuition\" style=\"\">Intuition<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/nth-fibonacci-number-introduction-to-dynamic-programming\/#10-detailed-approach\" style=\"\">Detailed Approach<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/nth-fibonacci-number-introduction-to-dynamic-programming\/#11-code\" style=\"\">Code<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/nth-fibonacci-number-introduction-to-dynamic-programming\/#12-code-explanation\" style=\"\">Code Explanation<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/nth-fibonacci-number-introduction-to-dynamic-programming\/#13-dry-run\" style=\"\">Dry Run<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/nth-fibonacci-number-introduction-to-dynamic-programming\/#14-time-and-space-complexity\" style=\"\">Time and Space Complexity<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/nth-fibonacci-number-introduction-to-dynamic-programming\/#15-simplifying-it\" style=\"\">Simplifying It<\/a><\/li><\/ul><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/nth-fibonacci-number-introduction-to-dynamic-programming\/#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\/nth-fibonacci-number-introduction-to-dynamic-programming\/#17-intuition\" style=\"\">Intuition<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/nth-fibonacci-number-introduction-to-dynamic-programming\/#18-detailed-approach\" style=\"\">Detailed Approach<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/nth-fibonacci-number-introduction-to-dynamic-programming\/#19-code\" style=\"\">Code<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/nth-fibonacci-number-introduction-to-dynamic-programming\/#20-code-explanation\" style=\"\">Code Explanation<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/nth-fibonacci-number-introduction-to-dynamic-programming\/#21-dry-run\" style=\"\">Dry Run<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/nth-fibonacci-number-introduction-to-dynamic-programming\/#22-time-and-space-complexity\" style=\"\">Time and Space Complexity<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/nth-fibonacci-number-introduction-to-dynamic-programming\/#23-simplifying-it\" style=\"\">Simplifying It<\/a><\/li><\/ul><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/nth-fibonacci-number-introduction-to-dynamic-programming\/#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\/nth-fibonacci-number-introduction-to-dynamic-programming\/#25-intuition\" style=\"\">Intuition<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/nth-fibonacci-number-introduction-to-dynamic-programming\/#26-detailed-approach\" style=\"\">Detailed Approach<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/nth-fibonacci-number-introduction-to-dynamic-programming\/#27-code\" style=\"\">Code<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/nth-fibonacci-number-introduction-to-dynamic-programming\/#28-code-explanation\" style=\"\">Code Explanation<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/nth-fibonacci-number-introduction-to-dynamic-programming\/#29-dry-run\" style=\"\">Dry Run<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/nth-fibonacci-number-introduction-to-dynamic-programming\/#30-time-and-space-complexity\" style=\"\">Time and Space Complexity<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/nth-fibonacci-number-introduction-to-dynamic-programming\/#31-simplifying-it\" style=\"\">Simplifying It<\/a><\/li><\/ul><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/nth-fibonacci-number-introduction-to-dynamic-programming\/#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 following a family tree where each person has exactly two parents! The most natural way to calculate the nth Fibonacci number is to directly implement the mathematical definition using recursion. Just like the definition says F(n) = F(n-1) + F(n-2), we make recursive calls to get these two values and add them together. It&#8217;s like asking &#8220;What&#8217;s my value?&#8221; and the answer is &#8220;Go ask my two parents what their values are, then add them up!&#8221; This continues until we reach the ancestors F(0) and F(1) who know their values directly.<\/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 n \u2264 1, return n directly (F(0) = 0, F(1) = 1).<\/li>\n\n\n\n<li><strong>Recursive Case<\/strong>: For n \u2265 2, return fib(n-1) + fib(n-2).<\/li>\n\n\n\n<li><strong>Direct Implementation<\/strong>: Translate the mathematical definition directly into code.<\/li>\n\n\n\n<li><strong>No Optimization<\/strong>: Make fresh recursive calls every time, even if we&#8217;ve calculated the same value before.<\/li>\n\n\n\n<li><strong>Tree Structure<\/strong>: Creates a binary tree of recursive calls with massive redundancy.<\/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:1rem;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 * 1rem);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 fib(self, num):\n        # Base cases: F(0) = 0, F(1) = 1\n        if num &lt;= 1:\n            return num\n        \n        # Recursive case: F(n) = F(n-1) + F(n-2)\n        return self.fib(num - 1) + self.fib(num - 2)\n\n    def nthFibonacci(self, n: int) -&gt; int:\n        return self.fib(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\">fib<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">num<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Base cases: F(0) = 0, F(1) = 1<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> num &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\"> num<\/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: F(n) = F(n-1) + F(n-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\">.fib(num - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">) + <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.fib(num - <\/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\">nthFibonacci<\/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\">.fib(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 is the most straightforward translation of the Fibonacci definition into code. The&nbsp;<code>fib<\/code>&nbsp;function handles the base cases where n \u2264 1 by returning n directly (this covers both F(0) = 0 and F(1) = 1). For any other value, it makes two recursive calls to get the previous two Fibonacci numbers and adds them together. The main function&nbsp;<code>nthFibonacci<\/code>&nbsp;simply calls the helper function. This approach creates a binary tree of recursive calls, where each node represents a function call.<\/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 = 5<\/code><\/p>\n\n\n\n<div class=\"wp-block-merpress-mermaidjs diagram-source-mermaid\"><pre class=\"mermaid\">graph TD\n    Root[\"fib(5)&lt;br\/>Check: 5 &lt;= 1? No&lt;br\/>Compute fib(4) + fib(3)\"]\n    \n    %% Level 1: F(5) branches to F(4) and F(3)\n    Root --- A[\"fib(4)&lt;br\/>Check: 4 &lt;= 1? No&lt;br\/>Compute fib(3) + fib(2)\"]\n    Root --- B[\"fib(3)&lt;br\/>Check: 3 &lt;= 1? No&lt;br\/>Compute fib(2) + fib(1)\"]\n    \n    %% Level 2: F(4) branches to F(3) and F(2)\n    A --- A1[\"fib(3)&lt;br\/>Check: 3 &lt;= 1? No&lt;br\/>Compute fib(2) + fib(1)\"]\n    A --- A2[\"fib(2)&lt;br\/>Check: 2 &lt;= 1? No&lt;br\/>Compute fib(1) + fib(0)\"]\n    \n    %% Level 2: F(3) branches to F(2) and F(1)\n    B --- B1[\"fib(2)&lt;br\/>Check: 2 &lt;= 1? No&lt;br\/>Compute fib(1) + fib(0)\"]\n    B --- B2[\"fib(1)&lt;br\/>Check: 1 &lt;= 1? Yes&lt;br\/>Return 1\"]\n    \n    %% Level 3: F(3) from F(4) branches to F(2) and F(1)\n    A1 --- A1a[\"fib(2)&lt;br\/>Check: 2 &lt;= 1? No&lt;br\/>Compute fib(1) + fib(0)\"]\n    A1 --- A1b[\"fib(1)&lt;br\/>Check: 1 &lt;= 1? Yes&lt;br\/>Return 1\"]\n    \n    %% Level 3: F(2) from F(4) branches to F(1) and F(0)\n    A2 --- A2a[\"fib(1)&lt;br\/>Check: 1 &lt;= 1? Yes&lt;br\/>Return 1\"]\n    A2 --- A2b[\"fib(0)&lt;br\/>Check: 0 &lt;= 1? Yes&lt;br\/>Return 0\"]\n    \n    %% Level 3: F(2) from F(3) branches to F(1) and F(0)\n    B1 --- B1a[\"fib(1)&lt;br\/>Check: 1 &lt;= 1? Yes&lt;br\/>Return 1\"]\n    B1 --- B1b[\"fib(0)&lt;br\/>Check: 0 &lt;= 1? Yes&lt;br\/>Return 0\"]\n    \n    %% Level 4: F(2) from A1 branches to F(1) and F(0)\n    A1a --- A1a1[\"fib(1)&lt;br\/>Check: 1 &lt;= 1? Yes&lt;br\/>Return 1\"]\n    A1a --- A1a2[\"fib(0)&lt;br\/>Check: 0 &lt;= 1? Yes&lt;br\/>Return 0\"]\n    \n    %% Results bubble up\n    A2a --- A2Result[\"F(2) = 1 + 0 = 1\"]\n    A2b --- A2Result\n    A2Result --- A_A2[\"Return 1 to F(4)\"]\n    \n    B1a --- B1Result[\"F(2) = 1 + 0 = 1\"]\n    B1b --- B1Result\n    B1Result --- B_B1[\"Return 1 to F(3)\"]\n    \n    A1a1 --- A1aResult[\"F(2) = 1 + 0 = 1\"]\n    A1a2 --- A1aResult\n    A1aResult --- A1_A1a[\"Return 1 to F(3)\"]\n    \n    A1b --- A1_A1b[\"Return 1 to F(3)\"]\n    A1_A1a --- A1Result[\"F(3) = 1 + 1 = 2\"]\n    A1_A1b --- A1Result\n    A1Result --- A_A1[\"Return 2 to F(4)\"]\n    \n    B2 --- B_B2[\"Return 1 to F(3)\"]\n    B_B1 --- BResult[\"F(3) = 1 + 1 = 2\"]\n    B_B2 --- BResult\n    BResult --- B_Final[\"Return 2 to F(5)\"]\n    \n    A_A1 --- AResult[\"F(4) = 2 + 1 = 3\"]\n    A_A2 --- AResult\n    AResult --- A_Final[\"Return 3 to F(5)\"]\n    \n    A_Final --- Final[\"F(5) = 3 + 2 = 5\"]\n    B_Final --- Final\n    Final --- Answer[\"Final Answer: 5\"]\n\n    %% Styling\n    style B2 fill:#90EE90\n    style A2a fill:#90EE90\n    style A2b fill:#90EE90\n    style B1a fill:#90EE90\n    style B1b fill:#90EE90\n    style A1a1 fill:#90EE90\n    style A1a2 fill:#90EE90\n    style A1b fill:#90EE90\n    style Answer fill:#90EE90\n    \n    style A2Result fill:#87CEEB\n    style B1Result fill:#87CEEB\n    style A1aResult fill:#87CEEB\n    style A1Result fill:#87CEEB\n    style BResult fill:#87CEEB\n    style AResult fill:#87CEEB\n    style Final fill:#87CEEB\n    \n    style Root fill:#E6E6FA\n<\/pre><\/div>\n\n\n\n<p>For detailed dry run [<strong><a href=\"https:\/\/mermaid.live\/edit#pako:eNqtVltv0zAU_iuW0SQm2hHbSdpaA9Rs7RPiYfACBFXO6q4VaVLlAoxp_x3HlyRul2Ya3cMSn8t3vu8c280DvE2XHFJ4l7HdGny5DhMg_m7StPgewtUmeu2dX0bZ2_dXa377kwIPXL4D6AP4lCprut2VBQdVoHsO3sgXch7CHwpH_T87Ax_5Lx4DRMFcAIIoY8ntmuegSIVBJLJkKV5EYl0dDIdDMNUcXIuD282BGA644VCjBRqNWGikGw0bNNSpCFMlwFZEjCKsFU2VHHQKBhoLayxsYeFuLGSwnONqyL4abNQgrSZQ7USnYKCxjBpkYSGN9ZXn0nzDizJLAOriTzT_VZZun5rLgZIp0oNhp9BSo0WnU4O71SCjxjFqsN4a7GX163zD37HynafznWfyJ738A6Q31gv51_mn4e-2-YvZ9nUfMbOZ0Av73yDg_1Rww_MyLnIQlVEUc1DuzIR1BawCRBUpUaCK7exUz9ZuiKxYY1Ur5VrIa8gIMdf5Hp1AywpQf1ExOyvWWFtFg4W8eeyiB7851RRMM5-hVXTcjq7tbblooW6K3tpREx8di1eIOrhFkxiaSDyxHR5Z4cZhT6XVINw1FWy6iY8xrLqtAvvpVVjtWG21ZjffJCw-YOcdtHBhLtNWWbcqi3VZ0nRlYS4uqyVWR_bKks6yMlAmmRT5xSLqibpYPL2W3L1gZW6M0yT_zbMKQprUkmqE-qh-Lu7jTXKn1rlY8Go2q00c01cTZzabOG1XdYK7fVGnrzqE3b7uPHmOjjiPMD2GKlvxhNuWo0eowsajq9kssHn3BDTHtzuir0YfQI9fjf7Q246RX6gqZObP_Pk0TOBAfJFvlpAWWckHcMuzLauW8KFKDGGx5lseQipel3zFql0Pw-RRpO1Y8i1NtyYzS8u7NaQrFudiVe6WrODXGyY-95sQnix5dpWWSQEpcSUEpA_wD6TY8y_cyWREfOISf-Q5owG8h3RI_AvkOdj1iIMmY2_seY8D-FeWRRfOaIxc5DrIn4w8__Efv3tkjg\" 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;\">Click here<\/span><\/mark><\/a><\/strong>]<\/p>\n\n\n\n<p><strong>Notice:<\/strong>&nbsp;fib(3), fib(2), fib(1), fib(0) are calculated 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, creating 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 asking your family tree for information but having a very forgetful family &#8211; every time you ask great-grandma her age, she forgets and has to ask her parents again, even if you just asked her 5 minutes ago! Very natural but extremely wasteful.<\/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 gave our forgetful family a notebook to write down answers so they don&#8217;t have to recalculate them? Memoization is exactly that &#8211; we store the results of expensive function calls and return the cached result when the same inputs occur again. Instead of recalculating fib(2) multiple times, we calculate it once, store the result, and look it up instantly next time. It&#8217;s like having a smart assistant who remembers previous calculations and can instantly tell you &#8220;Oh, you asked for fib(3) before &#8211; the answer is 2!&#8221;<\/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 a dp array of size n+1 with -1 (indicating uncomputed).<\/li>\n\n\n\n<li><strong>Check Cache First<\/strong>: Before computing, check if dp[num] != -1. If so, return cached result.<\/li>\n\n\n\n<li><strong>Compute and Store<\/strong>: If not cached, compute recursively and store in dp[num].<\/li>\n\n\n\n<li><strong>Same Recursive Structure<\/strong>: Keep the same recursive logic but add caching layer.<\/li>\n\n\n\n<li><strong>One-Time Computation<\/strong>: Each fib(k) is computed exactly once, then reused.<\/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:1rem;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 * 1rem);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 fib(self, num, dp):\n        # Base cases: F(0) = 0, F(1) = 1\n        if num &lt;= 1:\n            return num\n        \n        # Check if already computed (memoized)\n        if dp[num] != -1:\n            return dp[num]  # Return cached result\n        \n        # Compute and store in cache\n        dp[num] = self.fib(num - 1, dp) + self.fib(num - 2, dp)\n        return dp[num]\n\n    def nthFibonacci(self, n: int) -&gt; int:\n        # Initialize memoization array with -1 (uncomputed)\n        dp = [-1] * (n + 1)\n        return self.fib(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\">fib<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">num<\/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: F(0) = 0, F(1) = 1<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> num &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\"> num<\/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 (memoized)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> dp[num] != -<\/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[num]  <\/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 in cache<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        dp[num] = <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.fib(num - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, dp) + <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.fib(num - <\/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[num]<\/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\">nthFibonacci<\/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 with -1 (uncomputed)<\/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\">.fib(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 adds a memoization layer to the recursive approach. The&nbsp;<code>dp<\/code>&nbsp;array acts as our cache, initialized with -1 to indicate uncomputed values. Before making recursive calls, we check if&nbsp;<code>dp[num] != -1<\/code>&nbsp;&#8211; if true, we return the cached result immediately. If not cached, we compute the value recursively and store it in&nbsp;<code>dp[num]<\/code>&nbsp;before returning. This ensures each Fibonacci number is calculated exactly once, dramatically reducing the number of recursive calls from exponential to linear.<\/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 = 5<\/code><\/p>\n\n\n\n<div class=\"wp-block-merpress-mermaidjs diagram-source-mermaid\"><pre class=\"mermaid\">graph TD\n    Root[\"fib(5, dp=[-1,-1,-1,-1,-1,-1])&lt;br\/>Check: 5 &lt;= 1? No&lt;br\/>Check: dp[5] != -1? No (dp[5]=-1)&lt;br\/>Compute fib(4) + fib(3)\"]\n    \n    %% Level 1: F(5) branches to F(4) and F(3)\n    Root --- A[\"fib(4, dp)&lt;br\/>Check: 4 &lt;= 1? No&lt;br\/>Check: dp[4] != -1? No (dp[4]=-1)&lt;br\/>Compute fib(3) + fib(2)\"]\n    Root --- B[\"fib(3, dp)&lt;br\/>Check: 3 &lt;= 1? No&lt;br\/>Check: dp[3] != -1? Yes (dp[3]=2)&lt;br\/>Return dp[3] = 2 (Cache Hit!)\"]\n    \n    %% Level 2: F(4) branches to F(3) and F(2)\n    A --- A1[\"fib(3, dp)&lt;br\/>Check: 3 &lt;= 1? No&lt;br\/>Check: dp[3] != -1? No (dp[3]=-1)&lt;br\/>Compute fib(2) + fib(1)\"]\n    A --- A2[\"fib(2, dp)&lt;br\/>Check: 2 &lt;= 1? No&lt;br\/>Check: dp[2] != -1? Yes (dp[2]=1)&lt;br\/>Return dp[2] = 1 (Cache Hit!)\"]\n    \n    %% Level 3: F(3) branches to F(2) and F(1)\n    A1 --- A1a[\"fib(2, dp)&lt;br\/>Check: 2 &lt;= 1? No&lt;br\/>Check: dp[2] != -1? No (dp[2]=-1)&lt;br\/>Compute fib(1) + fib(0)\"]\n    A1 --- A1b[\"fib(1, dp)&lt;br\/>Check: 1 &lt;= 1? Yes&lt;br\/>Return 1 (Base Case)\"]\n    \n    %% Level 4: F(2) branches to F(1) and F(0) \n    A1a --- A1a1[\"fib(1, dp)&lt;br\/>Check: 1 &lt;= 1? Yes&lt;br\/>Return 1 (Base Case)\"]\n    A1a --- A1a2[\"fib(0, dp)&lt;br\/>Check: 0 &lt;= 1? Yes&lt;br\/>Return 0 (Base Case)\"]\n    \n    %% Results bubble up with memoization\n    A1a1 --- A1aResult[\"F(2) = 1 + 0 = 1&lt;br\/>Store: dp[2] = 1&lt;br\/>Return 1\"]\n    A1a2 --- A1aResult\n    A1aResult --- A1_A1a[\"Return 1 to F(3)\"]\n    \n    A1b --- A1_A1b[\"Return 1 to F(3)\"]\n    A1_A1a --- A1Result[\"F(3) = 1 + 1 = 2&lt;br\/>Store: dp[3] = 2&lt;br\/>Return 2\"]\n    A1_A1b --- A1Result\n    A1Result --- A_A1[\"Return 2 to F(4)\"]\n    \n    A2 --- A_A2[\"Return 1 (from cache)\"]\n    A_A1 --- AResult[\"F(4) = 2 + 1 = 3&lt;br\/>Store: dp[4] = 3&lt;br\/>Return 3\"]\n    A_A2 --- AResult\n    AResult --- A_Final[\"Return 3 to F(5)\"]\n    \n    B --- B_Final[\"Return 2 (from cache)\"]\n    \n    A_Final --- Final[\"F(5) = 3 + 2 = 5&lt;br\/>Store: dp[5] = 5&lt;br\/>Return 5\"]\n    B_Final --- Final\n    Final --- Answer[\"Final Answer: 5&lt;br\/>dp = [0, 1, 1, 2, 3, 5]\"]\n\n    %% Styling\n    style A1b fill:#90EE90\n    style A1a1 fill:#90EE90\n    style A1a2 fill:#90EE90\n    style Answer fill:#90EE90\n    \n    style A1aResult fill:#87CEEB\n    style A1Result fill:#87CEEB\n    style AResult fill:#87CEEB\n    style Final fill:#87CEEB\n    style B fill:#87CEEB\n    style A2 fill:#87CEEB\n    \n    style Root fill:#E6E6FA\n<\/pre><\/div>\n\n\n\n<p>For detailed dry run [<strong><a href=\"https:\/\/mermaid.live\/edit#pako:eNqtVltP2zAY_SvGE1IrWhbbSS8W3URL0R6mPcBetrZCTuPSaLkpTcYA8d_n-JImaQOTGKra-Luc850Tx-QZrmOPQwrvU5ZswferZQTE300cZ4sl3Phux-kBL5ks-qhX_6y6F2768dNsy9e_KHDAxQSgz-BbXI16ycJZgZMJ6MsU6MjApI90bxwmecZBQWN3wZm8IN0lXKkp1PfpKfjKf_MAIAquO04XuCmL1lu-A1ksAqKRRZ64EI3l7KDf74NLrcAuFNSmtdumtZvT2senJWZavJ-25J1qXnLAS9p4Scn7Q-jqyMgEq94bnuVppKsmAIPOjAn54IufnbR6hamypu4VMV5h7dWlMgq9Z2LtFDnuFDZOof2smhVrVnzAittY8YFPeDVBTZ9w4RP6J58IVbbUfcLGJ2R8Qtoo9p6ZtVP4uFPIOGVVnDK8ruZFB7xI8wpDqjYI-VO242AmvlrV21SJratHRr3VBWYMZvSj_zNIBdFsA-sA0TqOaL0u7Ybv8iDbATd33YCDPAEPfrYFIQ9j_4llfhyVI5R3VfWIQaQdxeY5EzTiV_LeZnHK6X5n1eRVJeE6XhlXS528U7uotEc_mQ0h4pbv693X6hWiLq4IIUYIKk6NhhB1lFSF4DqgWwM0iaqQO3lsmG5zGDdlYFOMqxo6mzQOwbp4PitC7sx2r6iwu_LMUypIQ4W9KoMamlTRcBVNR2sKrv2IBfu5iBLhNEVM1bHeLMfHZRh6WS07TZ_87yUGFmqw-HUaapxVGdQMTgk6bcKp8D54Ge0eeFqQyJBaUg3nJQJ5IR4wJD_i8BInvbOS6OVzc5s9Bn50r9Y7seByE278IKAfxtZ8PrbqOfH4vJLE7Uk525F0A0HfKlU3Gs7m82m94q2CN_LKqbbstB0XH0lVC-SbgCqZD-aD68tlBHviDcv3IM3SnPdgyNOQFUv4XDQuYbblIV9CKi49vmHFfoXL6EW0JSz6Gceh6Uzj_H4L6YYFO7HKE49l_Mpn4vUtLKMpjzyezuI8yiBFQ0eCQPoM_xRLcu6gMXGGw7EztLEtso-Q4tHwHNsjPLCRg8fOCNkvPfgkedG5KCYWsQdoPBpZI_vlL5U-17E\" 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;\">Click here<\/span><\/mark><\/a><\/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 fib(k) for k 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 giving everyone in your family tree a notebook where they write down their answers. The first time grandma calculates her value, she writes it down. Next time anyone asks, she just reads from her notebook instead of asking her parents again!<\/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 (asking for fib(n)) and working our way down to base cases, what if we start from the bottom (the base cases we know) and build our way up? Tabulation is like filling out a table row by row, where each row depends only on the previous rows we&#8217;ve already filled. We start with F(0) = 0 and F(1) = 1, then systematically compute F(2), F(3), F(4)&#8230; up to F(n). It&#8217;s like building a pyramid where each level is built on the solid foundation of the levels below it.<\/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>Handle Base Cases<\/strong>: Return n directly if n \u2264 1.<\/li>\n\n\n\n<li><strong>Initialize DP Array<\/strong>: Create dp array of size n+1, set dp = 0, dp = 1.<\/li>\n\n\n\n<li><strong>Bottom-Up Filling<\/strong>: For i from 2 to n, compute dp[i] = dp[i-1] + dp[i-2].<\/li>\n\n\n\n<li><strong>Sequential Order<\/strong>: Fill the array in increasing order so dependencies are always ready.<\/li>\n\n\n\n<li><strong>No Recursion<\/strong>: Pure iterative approach eliminates recursion stack overhead.<\/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:1rem;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 * 1rem);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 nthFibonacci(self, n: int) -&gt; int:\n        # Handle base cases\n        if n &lt;= 1:\n            return n\n        \n        # Initialize DP array\n        dp = [0] * (n + 1)\n        dp[0] = 0  # F(0) = 0\n        dp[1] = 1  # F(1) = 1\n        \n        # Fill array bottom-up\n        for i in range(2, n + 1):\n            dp[i] = dp[i - 1] + dp[i - 2]  # F(i) = F(i-1) + F(i-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\">nthFibonacci<\/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\"># Handle base cases<\/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\"> n<\/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 DP array<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        dp = [<\/span><span style=\"color: #B5CEA8\">0<\/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\">0<\/span><span style=\"color: #D4D4D4\">  <\/span><span style=\"color: #6A9955\"># F(0) = 0<\/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\"># F(1) = 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\"># 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\"> i <\/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[i] = dp[i - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">] + dp[i - <\/span><span style=\"color: #B5CEA8\">2<\/span><span style=\"color: #D4D4D4\">]  <\/span><span style=\"color: #6A9955\"># F(i) = F(i-1) + F(i-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 eliminates recursion entirely by building the solution from the ground up. We first handle the base cases directly. Then we create a dp array and initialize the known values dp = 0 and dp = 1. The for loop fills the array from index 2 to n, where each dp[i] is computed using the previously computed values dp[i-1] and dp[i-2]. Since we fill the array sequentially, these dependencies are always available when we need them. This approach is more space and time efficient than memoization because it avoids recursion overhead.<\/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<div class=\"wp-block-merpress-mermaidjs diagram-source-mermaid\"><pre class=\"mermaid\">graph TD\n    Root[\"nthFibonacci(5)&lt;br\/>Check: 5 &lt;= 1? No&lt;br\/>Initialize dp = [0,0,0,0,0,0] (size 6)\"]\n    \n    %% Initialization\n    Root --- Init[\"Base Case Setup&lt;br\/>dp[0] = 0 (F(0) = 0)&lt;br\/>dp[1] = 1 (F(1) = 1)&lt;br\/>dp = [0,1,0,0,0,0]\"]\n    \n    %% Loop iterations\n    Init --- Loop[\"for i in range(2, 6):&lt;br\/>Fill dp array bottom-up\"]\n    \n    %% Iteration i=2\n    Loop --- I2[\"i=2: Compute F(2)&lt;br\/>dp[2] = dp[1] + dp[0]&lt;br\/>dp[2] = 1 + 0 = 1&lt;br\/>dp = [0,1,1,0,0,0]\"]\n    \n    %% Iteration i=3\n    I2 --- I3[\"i=3: Compute F(3)&lt;br\/>dp[3] = dp[2] + dp[1]&lt;br\/>dp[3] = 1 + 1 = 2&lt;br\/>dp = [0,1,1,2,0,0]\"]\n    \n    %% Iteration i=4\n    I3 --- I4[\"i=4: Compute F(4)&lt;br\/>dp[4] = dp[3] + dp[2]&lt;br\/>dp[4] = 2 + 1 = 3&lt;br\/>dp = [0,1,1,2,3,0]\"]\n    \n    %% Iteration i=5\n    I4 --- I5[\"i=5: Compute F(5)&lt;br\/>dp[5] = dp[4] + dp[3]&lt;br\/>dp[5] = 3 + 2 = 5&lt;br\/>dp = [0,1,1,2,3,5]\"]\n    \n    %% Final result\n    I5 --- Final[\"Loop Complete&lt;br\/>Return dp[5] = 5\"]\n    Final --- Answer[\"Final Answer: 5&lt;br\/>Complete DP Array: [0,1,1,2,3,5]\"]\n\n    %% Show dependency relationships\n    I2 --- Dep2a[\"Uses: dp[1]=1\"]\n    I2 --- Dep2b[\"Uses: dp[0]=0\"]\n    \n    I3 --- Dep3a[\"Uses: dp[2]=1 (computed)\"]\n    I3 --- Dep3b[\"Uses: dp[1]=1 (base)\"]\n    \n    I4 --- Dep4a[\"Uses: dp[3]=2 (computed)\"]\n    I4 --- Dep4b[\"Uses: dp[2]=1 (computed)\"]\n    \n    I5 --- Dep5a[\"Uses: dp[4]=3 (computed)\"]\n    I5 --- Dep5b[\"Uses: dp[3]=2 (computed)\"]\n\n    %% Styling\n    style Answer fill:#90EE90\n    style Final fill:#90EE90\n    \n    style I2 fill:#87CEEB\n    style I3 fill:#87CEEB\n    style I4 fill:#87CEEB\n    style I5 fill:#87CEEB\n    \n    style Dep2a fill:#FFE4B5\n    style Dep2b fill:#FFE4B5\n    style Dep3a fill:#FFE4B5\n    style Dep3b fill:#FFE4B5\n    style Dep4a fill:#FFE4B5\n    style Dep4b fill:#FFE4B5\n    style Dep5a fill:#FFE4B5\n    style Dep5b fill:#FFE4B5\n    \n    style Root fill:#E6E6FA\n    style Init fill:#E6E6FA\n<\/pre><\/div>\n\n\n\n<p>For detailed dry run [<strong><a href=\"https:\/\/mermaid.live\/edit#pako:eNqNlmtvmzAUhv-K5akS0ZIOfMkFjU1tGqRJ0zS125c1fIDgJGgEIzDq0qr_fb4QAilNm0iAz3suz8HG8ARXPGbQhZsizLfg180yA_J3y7m4X8JMbP0k4lm4WiUWHXyOik9f5lu2-usCCj57wPkKfnBt_ZYlIgnT5JGBOAceuLeHzT8AVqmE8WAJA5PfHC8uQBMXioRnx-JgNBppUVJchyUDc3W4Y6LKdb04v5d5PWADy7fsgboaHARHCY4SHCU4B8FgOQ3WS5rvnOcgEazQNKWxKwqNo1SJs-YFSECSgSLMNsxCQ9mYq0v4SZqq9sOiCPcg4kLw3ajKe7o-lACJh4xVl9ZNI1lDml0w57u8Egz4Fmp6Q6o30-NHoG9CR3Gk1Vbnk5adV1tuo-C6YWRAsAbBbRDcgOAaBNUgTtBRFIgjz-gFCHoHCKlBsAEhGoS0QUgDQmoQXIOgoKOgGgT3gOA3QWgNQgwI1SC0DUIbEFqDkBoEBx0FSyuSZ9oLQntA_CQLU1CwskpFzUE1hxYkil4zCiVlgum0t_IBKTJwqEmbpCaXCr7KygdWyGhjMkO3xjokAzc_wZVaxW4PZAN4t-UPIGY5y2KWrfYSNTUPzjbJy85aumE5CmXN3yUrXbNcPKeBazlFbSc78OyT21IvCemKO_mQzAeslZmW-LjRtPyj0_rAiuSmcrop1XMtI0inAg481Fvh6B-9h6gzkzKKdqqQwMO9VY7-0VtUx_kR-zTJNmZcygGrpxus5U7lfpjZi8XMbstmTbxU2z5ytozDdDJfLK47En5dIq9LtEdqO-jVU_v4_oJc01M1Oqfis7H4bCw5G0vOxtKzsbQvtu2jX4PGZTFejP2rzj1TL6WuCIfyJZ7E0BVFxYZwx4pdqIbwSQUuodiyHVtCV17GbB2qTQUus2cZlofZH853h8iCV5stdNdhWspRlcehYDdJKL8Qdo21UM98MedVJqBLZ45OAt0n-A-6iNBLjKeTGcXYxlPskCHcQ3dEML2cOLY9nth0RukUPw_ho67rXCKECZraU0SlF7bR83_nqHIk\" 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;\">Click here<\/span><\/mark><\/a><\/strong>]<\/p>\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, each iteration is O(1)<\/li>\n\n\n\n<li><strong>Space Complexity:<\/strong>&nbsp;O(n) &#8211; dp array of size n+1, no recursion stack<\/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 staircase step by step &#8211; you place the first step (F(0)), then the second step (F(1)), then for each new step you only need to look at the two steps directly below it to know how high to build it. Very systematic and efficient!<\/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>Looking at our tabulation approach, do we really need to store ALL the Fibonacci numbers from 0 to n? Actually, to calculate any Fibonacci number, we only need the previous two numbers! It&#8217;s like climbing stairs where you only need to remember the height of the last two steps to determine the height of the next step. This insight allows us to reduce our space usage from O(n) to O(1) by keeping track of only the last two computed values instead of the entire array.<\/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>Handle Base Cases<\/strong>: Return n directly if n \u2264 1.<\/li>\n\n\n\n<li><strong>Two Variables<\/strong>: Use prev2 = F(0) = 0 and prev = F(1) = 1.<\/li>\n\n\n\n<li><strong>Sliding Window<\/strong>: For each new Fibonacci number, compute curr = prev + prev2.<\/li>\n\n\n\n<li><strong>Update Variables<\/strong>: Slide the window by setting prev2 = prev, prev = curr.<\/li>\n\n\n\n<li><strong>Constant Space<\/strong>: Only store 2-3 variables regardless of input size.<\/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:1rem;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 * 1rem);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 nthFibonacci(self, n: int) -&gt; int:\n        # Handle base cases\n        if n &lt;= 1:\n            return n\n        \n        # Initialize the first two Fibonacci numbers\n        prev2 = 0  # F(0)\n        prev = 1   # F(1)\n        \n        # Compute from F(2) to F(n)\n        for i in range(2, n + 1):\n            curr = prev + prev2  # F(i) = F(i-1) + F(i-2)\n            prev2 = prev         # Slide window: F(i-2) becomes F(i-1)\n            prev = curr          # Slide window: F(i-1) becomes F(i)\n        \n        return prev  # prev now contains F(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\">nthFibonacci<\/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\"># Handle base cases<\/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\"> n<\/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 the first two Fibonacci numbers<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        prev2 = <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">  <\/span><span style=\"color: #6A9955\"># F(0)<\/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\"># F(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\"># Compute from F(2) to F(n)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> i <\/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\"># F(i) = F(i-1) + F(i-2)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            prev2 = prev         <\/span><span style=\"color: #6A9955\"># Slide window: F(i-2) becomes F(i-1)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            prev = curr          <\/span><span style=\"color: #6A9955\"># Slide window: F(i-1) becomes F(i)<\/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 contains F(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 uses the key insight that we only need the last two Fibonacci numbers to compute the next one. We maintain two variables:&nbsp;<code>prev2<\/code>&nbsp;(representing F(i-2)) and&nbsp;<code>prev<\/code>&nbsp;(representing F(i-1)). In each iteration, we compute the current Fibonacci number as&nbsp;<code>curr = prev + prev2<\/code>, then slide our &#8220;window&#8221; by updating prev2 = prev and prev = curr. This creates a sliding window effect where we always maintain the two most recent values. After the loop,&nbsp;<code>prev<\/code>&nbsp;contains F(n). This approach has the same time complexity as tabulation but uses only constant extra 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 = 0 (F(0)), prev = 1 (F(1))<\/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 + 0 = 1 (this is F(2))<\/li>\n\n\n\n<li>prev2 = prev = 1, prev = curr = 1<\/li>\n\n\n\n<li><strong>State: prev2 = 1 (F(1)), prev = 1 (F(2))<\/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 = 1 + 1 = 2 (this is F(3))<\/li>\n\n\n\n<li>prev2 = prev = 1, prev = curr = 2<\/li>\n\n\n\n<li><strong>State: prev2 = 1 (F(2)), prev = 2 (F(3))<\/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 = 2 + 1 = 3 (this is F(4))<\/li>\n\n\n\n<li>prev2 = prev = 2, prev = curr = 3<\/li>\n\n\n\n<li><strong>State: prev2 = 2 (F(3)), prev = 3 (F(4))<\/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 = 3 + 2 = 5 (this is F(5))<\/li>\n\n\n\n<li>prev2 = prev = 3, prev = curr = 5<\/li>\n\n\n\n<li><strong>State: prev2 = 3 (F(4)), prev = 5 (F(5))<\/strong><\/li>\n<\/ul>\n\n\n\n<p><strong>Return prev = 5<\/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, each iteration is O(1)<\/li>\n\n\n\n<li><strong>Space Complexity:<\/strong>&nbsp;O(1) &#8211; Only using 3 variables regardless of input size<\/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 being a very memory-efficient climber who only remembers the heights of the last two steps they climbed. As they climb each new step, they forget the older steps but always remember the two most recent ones, which is all they need to determine the next step&#8217;s height!<\/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 + 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 clearly the best approach for production use, offering optimal time complexity with minimal space usage. However, each approach teaches valuable concepts:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Pure Recursion<\/strong>&nbsp;shows the natural mathematical definition<\/li>\n\n\n\n<li><strong>Memoization<\/strong>&nbsp;introduces the concept of caching expensive computations<\/li>\n\n\n\n<li><strong>Tabulation<\/strong>&nbsp;demonstrates systematic bottom-up problem solving<\/li>\n\n\n\n<li><strong>Space Optimization<\/strong>&nbsp;shows how to identify and eliminate unnecessary storage<\/li>\n<\/ul>\n\n\n\n<p>The progression from exponential recursion to optimal O(n) time and O(1) space beautifully illustrates the power of dynamic programming optimization techniques!<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\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<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\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Given a non-negative integer&nbsp;n, your task is to find the&nbsp;nth&nbsp;Fibonacci&nbsp;number. The&nbsp;Fibonacci sequence&nbsp;is a sequence where the next term is the sum of the previous two terms. The first two terms of the Fibonacci sequence are 0 followed by 1. The Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21. Here&#8217;s the [Problem Link]<\/p>\n","protected":false},"author":1,"featured_media":779,"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-776","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\/fibonacci-dynamic-programming-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\/776","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=776"}],"version-history":[{"count":3,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/776\/revisions"}],"predecessor-version":[{"id":783,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/776\/revisions\/783"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media\/779"}],"wp:attachment":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media?parent=776"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/categories?post=776"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/tags?post=776"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}