Dynamic Programming

Understanding Dynamic Programming in Two Stages

Dynamic programming (DP) is a way to solve complex problems by breaking them into smaller, overlapping subproblems. It is especially useful when the same subproblems are solved many times in a simple recursive solution.

A good way to build a dynamic programming algorithm is to go through two main stages:

Stage 1: Develop a Recursive Solution

The first step is to describe the problem in terms of smaller versions of itself.

 (a) Specification

You must clearly define what your recursive function does. For example, for the Fibonacci sequence:

Fibonacci series

The Fibonacci sequence starts with 0 and 1, and every number after that is the sum of the previous two.

(b) Recursive Formula

Here is the recursive function written formally:This definition expresses the problem in terms of smaller subproblems: computing `F(n-1)` and `F(n-2)`.

The recursive version is easy to understand but slow, because it repeats many calculations.

Stage 2: Build the Dynamic Programming Algorithm

Once we have the recursive definition, we can make it efficient by storing results of subproblems so we do not compute the same thing multiple times.

We can do this step-by-step.

(a) Identify the Subproblems

The subproblems here are F(0), F(1), F(2), …, up to F(n).

(b) Choose a Memoization Data Structure

We can use an array `F[0..n]` to store the Fibonacci numbers.

(c) Identify Dependencies

Each `F[i]` depends on two earlier values: `F[i-1]` and `F[i-2]`.

(d) Find a Good Evaluation Order

We should compute values starting from the smallest, because each new value depends on smaller ones.

That means we start from the base cases and move upward:

* Compute F[0]

* Compute F[1]

* Then compute F[2], F[3], …, F[n]

(e) Analyze Space and Time

There are n subproblems, each taking constant time to compute.

So, the total running time is O(n).

The array uses O(n) space.

(f) Write the Algorithm

Here is the final dynamic programming version in code:

def fib(n):
    F = [0] * (n + 1)
    F[0] = 0
    if n > 0:
        F[1] = 1
    for i in range(2, n + 1):
        F[i] = F[i - 1] + F[i - 2]
    return F[n]

This algorithm computes each Fibonacci number once and stores it for reuse.

Summary

To design a dynamic programming algorithm:

1. Define the problem recursively.

2. Identify subproblems and build the solution bottom-up.

Using this two-stage approach makes complex problems simpler and more efficient to solve.