Static vs. Dynamic Programming: Memory & Algorithms Guide

Static vs. Dynamic Programming

A Comprehensive Guide to Memory Management & Algorithms

In-Depth Explanation for Exams & Interviews

1. Static Programming

Static programming refers to programs where memory allocation, structure, and control flow are decided at compile time. Everything is fixed before the program runs, leading to high speed but low flexibility.

Key Characteristics: Static

<strong>Allocated at Compile Time:</strong> Memory size is fixed and cannot grow or shrink during execution.

<strong>High Speed & Efficiency:</strong> Less overhead means faster execution and predictable performance.

<strong>Rigid Structure:</strong> Runtime changes to memory size are not allowed.

<strong>Examples:</strong> C (static arrays), C++, Java (static variables).

Static Code Example (C)

int arr[10]; // Array size is fixed int a = 10; // Value fixed at init int b = 20; int sum = a + b; // Values, Memory, and Flow are fixed at compile time.

Two Meanings of Dynamic Programming

1. Dynamic Memory (Runtime Management) 2. Dynamic Programming (Algorithm Optimization)

A. Dynamic Memory Allocation

Memory is allocated during execution (Runtime). It adapts based on input size, allowing the program to grow or shrink as needed using functions like malloc(), calloc(), and free().

B. Dynamic Programming (Algorithm)

DP is an optimization technique used to solve complex problems by breaking them into smaller overlapping subproblems. It stores the results of these subproblems (Memoization) to avoid repeated calculations, drastically improving performance.

Core Properties of DP

<strong>Overlapping Subproblems:</strong> The problem can be broken down into smaller problems which are reused multiple times.

<strong>Optimal Substructure:</strong> An optimal solution can be constructed efficiently from optimal solutions of its subproblems.

<strong>Storage (Cache):</strong> Results are stored in a table or array to ensure no computation is performed twice.

Tw0 Main DP Approaches

<strong>1. Top-Down (Memoization):</strong> Uses recursion. It starts from the main problem and breaks it down, storing results in a map or array.

<strong>2. Bottom-Up (Tabulation):</strong> Uses loops (iteration). It starts from the smallest subproblems (base cases) and builds up to the final answer.

<strong>Key Difference:</strong> Recursion vs. Iteration. Bottom-up avoids stack overflow issues common in deep recursion.

Static vs. Dynamic: Final Comparison

<strong>Decision Time:</strong> Compile Time (Static) vs. Runtime (Dynamic)

<strong>Memory:</strong> Fixed Size (Static) vs. Flexible/Resizable (Dynamic)

<strong>Speed:</strong> Very Fast (Static) vs. Slightly Slower (Dynamic)

<strong>Optimization:</strong> None (Static) vs. Subproblem Caching (Dynamic)

Classic DP Use Cases

<ul><li><strong>Fibonacci:</strong> Optimization of recursion.</li><li><strong>Knapsack Problem:</strong> Resource allocation.</li><li><strong>Longest Common Subsequence:</strong> Text comparison/Diff tools.</li><li><strong>Shortest Path Algorithms:</strong> Maps and Routing sets.</li><li><strong>AI & Finance:</strong> Complex decision making.</li></ul>