04 Fibonacci Numbers Dynamic Programming Bottom Up

Rishi Srivastava Using Dynamic Programming Bottom up approach, we use the tabulation technique through iteration. Starting from the smallest subproblem, we store the results in a table (an array), do something with the data (for example: add the data for Fibonacci) until we arrive at the solution. Dynamic Programming Bottom Up pseudocode: function fibBottomUp(n) if (n 0, , n 1) return n; long dp new longn; dp0 0; dp1 1; for (int i 2; i is less than n; i++) dpi dpi 1 + dpi 2; return dpn 1 + dpn 2; Time complexity: O(n) Space complexity: O(n) Github: Leetcode: