Dynamic Programming

Contents

1. Recursion
2. The Dynamic Programming
3. How to build a DP
4. Problems to practice

Recursion

One previous knowledge we have to know before starting with Dynamic Programming is recursion.

Recursion is the process in which a function calls itself directly, or indirectly. The corresponding function is called a recursive function.

In general, recursion is a versatile and powerful tool that can be used to solve many different types of problems. This, because recursion helps in logic building, recursive thinking helps in solving complex problems by breaking them into smaller subproblems, making easier the process of solving a problem if you shatter it into small pieces, and solve these pieces instead of all the problem, every time you know that you can decompose the original problem into that chunks.

A recursive algorithm takes one step toward a solution, and then, recursively calls itself to move further. The algorithm stops once we reach the solution.

How to implement recursion on a problem?


1st Step
Define a base case: Identify the simplest (or base) case for which the solution is known or trivial. This will be the stop condition for the recursion (Preventing it from infinitely calling itself and never-ending). There can be more than one base condition in a recursion.


2nd Step
Define a recursive case: Define the problem in terms of smaller subproblems. Break the problem down into smaller versions of itself, and call the function recursively to solve each subproblem. Logic is built in terms of smaller problems. The primary property of recursion is the ability to solve a problem by breaking it down into smaller sub-problems, each of which can be solved in the same way.


3rd Step
Ensure the recursion terminates: Make sure that the recursive function eventually reaches the base case, and does not enter an infinite loop, for every valid input. The recursion terminates when the base case becomes true.


4th Step
Combine the (sub)solutions: Combine the solutions of the subproblems to solve the original problem.

With great power, comes great responsibility.

It is important to know the consequences of applying recursion to a problem/algorithm, not all are as beautiful as they seem.

Recursivity is another approach to iterative functions. Usually, an algorithm that can be thought iterative (code inside a for-while loop) can also be thought as recursive (code inside a recursive function), even when not always a recursive algorithm can translate into an iterative one and vice versa, the recursion is often related/compared to iterative algorithms.

One of the advantages of using recursion is:

• Provides a clean and simple way to write code.
• Can be more readable and easy to understand. (Simplify complex problems)
• Some problems are inherited recursively.

But there are also disadvantages to recursion that need to be considered:

• Can be less efficient than iterative solutions in terms of memory and performance.
• Can lead to to stack overflow errors if the recursion depth is too high.
• Doing (time) complexity analysis could be harder than iterative versions.

The biggest warning about using recursion is the second disadvantage, the call stack. A process is called in every recursive call, and it doesn't end until after all recursive calls get to a base case. If this takes a lot of recursive calls, can lead to a Memory Limit Exceed (MLE) verdict. Because of this, is a good idea to be able to translate every algorithm we recursively implement in it iterative way, just in case the judge doesn't accept it.
Also is pretty easy to get exponential time complexities when working with recursion, that's another thing to keep in mind.

There exist some algorithms native known as recursively: Hannoi's Towers Problem, DFS graph traversal, Binary Search, sorting algorithms such as Merge Sort or Quick Sort, and Preorder/Inorder/Postorder Tree Traversals...

Recursion is the basis of other techniques and solving problem paradigms, such as Divide and Conquer and, of course, Dynamic Programming.

The Dynamic Programming

Dynamic Programming (just DP until now) is a technique and one of the main problem-solving paradigms:

• Complete Search
• Greedy
• Divide and Conquer
• Dynamic Programming

DP combines the correctness of complete search and the efficiency of greedy algorithms. Can be applied if the problem can be divided into overlapping subproblems that can be solved independently. There are two uses for DP:

1. Finding an optimal solution: We want to find a solution that is as large as possible,
   or as small as possible.
2. Counting the number of solutions: We want to calculate the total number of
   possible solutions. Problems of the type How many possible ways are there to do a certain thing?

Understanding DP is a milestone in every competitive programmer's career.
While the basic idea is simple, the challenge is how to apply DP to different problems. The only way to learn DP is by solving problems that involve DP.

DP is also the optimization that comes when greedy fails. Both are, naturally, different paradigms that approach one problem in different ways, is common that the first approach from a competitor to a problem is greedy, but when things start to get rough and the local decision becomes abstract or nonviable, DP shows up as a better approach.

DP refers to simplifying a complicated problem by breaking it down into simpler sub-problems in a recursive manner. But it is an optimization over plain recursion, the essence of DP is to avoid repeated calculation.

The idea is to simply store the results of subproblems so that we do not have to re-compute them when needed later. This simple optimization typically reduces time complexities from exponential to polynomial.

Not all problems can be solvable with DP. Intuitively, those that can be solved with DP are problems with overlapping subproblems so we can avoid the redundancy on them.
DP is not magic! It's the result of smart recursion + storage.

When to use DP?


1st Case
The problem has an optimal substructure: A given problem is said to have Optimal Substructure Property if the optimal solution of the given problem can be obtained by using the optimal solution to its subproblems instead of trying every possible way to solve the subproblems.

This property is utilized to plan dynamic programming calculations that tackle streamlining issues by separating them into more modest subproblems and afterward consolidating the answers for those subproblems to get an answer for the first issue. To show this thought all the more officially, we should assume we disapprove of an ideal arrangement \( S^* \) and a bunch of subproblems \( S_1, S_2, \dots, S_n \). On the off chance that the ideal answer for the issue can be developed from the ideal answers for the subproblems, then the issue displays the ideal base property. \[ S^* = S_1 \cup S_2 \cup \dots \cup S_n \]


2nd Case
The problem have overlapping subproblems: Like Divide and Conquer, Dynamic Programming combines solutions to sub-problems. Dynamic Programming is mainly used when solutions to the same subproblems are needed again and again. In dynamic programming, computed solutions to subproblems are stored in a table so that these don't have to be recomputed. So Dynamic Programming is not useful when there are no common (overlapping) subproblems because there is no point in storing the solutions if they are not needed again.

For example, Binary Search doesn't have common subproblems. If we take the example of following a recursive program for Fibonacci Numbers, there are many subproblems that are solved again and again.

How to build a DP

There are two approaches (ways to store the values so that these values can be reused) when we're using DP for solving overlapping subproblems:

• Memoization (Top-Down)
• Tabulation (Bottom-Up)

Memoization

Memoization is a recursive approach where the solution to a problem is built by solving smaller subproblems first.
It uses a memo table (DP storage) to store results already computed.
The recursion starts from the top (original problem) and breaks it down into smaller sub-problems (Top \(\rightarrow\) Down).

How to implement it?

1. Define a recursive function that solves the problem.
2. Check the memo table before computing a subproblem.
   • If the result is already stored, return it.
   • Otherwise, compute it recursively and store the resutl.
3. Handle the smallest (base) cases.

Advantages:

• Intuitive to implement. (Follows natural problem breakdown)
• Only computes necessary subproblems. (Lazy evaluation)

Disadvantages:

• Recursion overhead. (Stack overflow for deep recursion)
• Slower than tabulation due to function calls.

Tabulation

Tabulation is a iterative approach where solutions to subproblems are computed in a fixed order, usually from smallest to largest.
It fills a table (DP array) in a structured way, starting from base cases and building up to the final solution (Bottom \(\rightarrow\) Up).

How to implement it?

1. Initialize a DP table (dp[]) with base cases.
2. Iterate through states in a predefined order. (loop)
3. Compute each state using previously computed states.

Advantages:

• No recursion overhead. (Faster in practice)
• Often more space-optimizable. (e.g., using only last few states)

Disadvantages:

• May compute unnecessary subproblems.
• Requires careful ordering of computations.

State Transition Styles

The terms push and pull describes how DP state transitions are formulated in both memoization and tabulation.

Pull DP
Pull from previous states. The current state dp[i] pulls its value from previously computed states. What previous states contribute to dp[i]?
Current state pulls from past.
How do I compute dp[i]?
Backward-looking.
dp[i] = dp[i-1] + dp[i-2] \(\leftarrow\) Pulls from i-1 and i-2

Push DP
Push to future states. The current state dp[i] pushes its value to future states. What future states does dp[i] influence?
Current state pushes to future.
Forward-looking.
Where does dp[i] contribute?
dp[i+1] += dp[i]; dp[i+2] += dp[i] \(\leftarrow\) Pushes to i+1 and i+2

Steps to solve DP problems:

1. Identify if DP is applicable. Optimal substructure / Overlapping subproblems.
2. Define DP state. What does dp[i][j] represent? A state can be defined as the set of parameters that can uniquely identify a certain position or standing in the given problem. This set of parameters should be as small as possible to reduce state space.
3. Formulate the recurrence relation. How does dp[i] depend on other states, how to pass from dp[i] to dp[i+1]. Formulating a relation between the states is the hardest part of solving a Dynamic Programming problem and requires a lot of intuition, observation, and practice.
4. Set base cases. Smallest, intuitive, obvious subproblems.
5. Choose memoization or tabulation. Top-Down or Bottom-Up approach, recursive or iterative implementation.

Problems to practice!