Dynamic Programming
Dynamic Programming
Dynamic Programming (DP) is a method for solving complex problems by breaking them down into simpler, overlapping subproblems. It solves subproblems once and stores their solutions using Memoization (Top-down) or Tabulation (Bottom-up), trading memory to optimize computational speed.
Complexity Profile
| Case | Complexity |
|---|---|
| Best Case | O(Decision States) |
| Average Case | O(Decision States) |
| Worst Case | O(Decision States) |
| Space Complexity | O(States) |
Code Implementation
# DP: Fibonacci with Memoization (Top-Down)
def fib_memo(n, memo=None):
if memo is None:
memo = {}
if n <= 1:
return n
if n in memo:
return memo[n]
memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
return memo[n]
# Tabulation approach (Bottom-Up)
def fib_tab(n):
if n <= 1:
return n
table = [0] * (n + 1)
table[1] = 1
for i in range(2, n + 1):
table[i] = table[i - 1] + table[i - 2]
return table[n]Real-World Applications
- Knapsack resource allocation optimizations.
- String edit distance (Levenshtein distance) in spellchecking.
- Pathfinding inside grids with variable terrains (Viterbi algorithm).
Naive Bayes
Naive Bayes is a probabilistic classifier based on Bayes' Theorem. It makes the 'naive' assumption that features are conditionally independent of each other given the class label, which simplifies joint probability calculation and enables fast training speeds on large datasets.
A*
A* (A-Star) is a heuristic-guided pathfinding algorithm. It extends Dijkstra's by calculating f(n) = g(n) + h(n), where g(n) is the exact cost to reach node n, and h(n) is a heuristic estimating the distance from n to the goal. Best-first search that minimizes explored graph nodes.