Skip to content

Files

Latest commit

 

History

History
50 lines (29 loc) · 1.32 KB

MEMOIZATION-AND-DYNAMIC-PROGRAMMING.md

File metadata and controls

50 lines (29 loc) · 1.32 KB

Memoization and Dynamic Programming

Memoization and dynamic programming are techniques used to optimize algorithms by avoiding redundant calculations and storing intermediate results for future use

Memoization

Memoization involves caching the results of function calls to avoid calculations. It is often used in combination with recursion

Dynamic Programming

Dynamic programming is a technique for solving problems by breaking them down into overlapping sub-problems and storing the solutions to sub-problems in a table to avoid redundant calculations

Example

This is an example of memoization and dynamic programming

Fibonacci Sequence

def fib(n, memo = {})
  if (n === 0 || n === 1) return n

  if (!memo[n])
    return (memo[n] = fibonacci(n - 2, memo) + fibonacci(n - 1, memo))

  return memo[n]
end

When to use Memoization and Dynamic Programming

  • When you need to optimize a recursive algorithm
  • When solving problems that can be broken down into smaller sub-problems and have an optimal substructure

References

 

 

Go To Top   ⬆️

← Go Back