Dynamic Programming

Dynamic programming is an optimization technique that aims to solve large and complex problems by breaking them down into smaller subproblems. The solutions to these subproblems are stored to avoid recomputation, thereby saving time and source resources.

Applications

• Computer Science - Shortest path algorithms (e.g., Floyd-Warshall algorithm), sequence alignment, data compression.
• Economics - Decision-making models, inventory control.
• Artificial Intelligence - Evaluation of game trees, reinforcement learning algorithms.

Core Principles

• Overlapping Subproblems - This means the problem can be divided into smaller subproblems whose solutions overlap. The presence of overlapping subproblems implies that the solution to one subproblem is part of the solution to another subproblem.
• Optimal Substructure - This means the optimal solution to a problem can be constructed from optimal solutions to its smaller subproblems. Therefore, a problem must not only have overlapping subproblems but also exhibit optimal substructure, so that the solutions to the subproblems can be combined to form the overall solution.

Methods Used

• Memoization (top-down approach) - A technique where the solution is found recursively. As the algorithm runs, solutions to subproblems are stored, and before attempting to compute a subproblem’s solution, it first checks whether that solution has already been computed to avoid redundant calculations.
• Tabulation (bottom-up approach) - Solutions to overlapping subproblems are stored in a table, starting from the most basic subproblems and building up toward the final solution.

Example Problem: Finding the Fibonacci Sequence

The Fibonacci sequence is a series of numbers in which each number is the sum of the two preceding ones. For example,

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, ...

Below are examples in C++ for computing Fibonacci numbers.

1- Using Memoization

2- Using Tabulation