Unlocking Efficiency: Dynamic Programming- Solving Problems with 99% Less Crying and 100% More Algorithms (No Tears, Just Cheers!)

This quote is always written when starting with dynamic programming :
“Those who Forget the Past, are condemned to Repeat it”

[Pre-Requisite of Dynamic Programming] : Recursion

What is Dynamic Programming ?

=> The Term Dynamic Programming was Coined by Richard Bellman in the 1950s.

=> The Term “Dynamic Programming” consist of Two words:
1- Dynamic : It Refers to the process of solving a complex problem by breaking it down into Simpler Sub-problems and solving those Sub-problems optimally.
2- Programming : In “Dynamic Programming” it means “Table Filling”

=> Dynamic Programming is a Technique used in Computer Science & Mathematics to solve problems by breaking them down into simpler
Sub-problems and solving each sub-problem once, Storing the solution
in a table to avoid redundant computations.
=> It is a General and Powerful Paradigm for Algorithm Design.

Use Of Dynamic Programming ?

=> It is Particularly Useful for optimization problems, where you need to
find the best solution from a set of possible solutions :
> Finding a Solution with the Optimal Value.
Optimal : Maximization / Minimization

Goals : “Our Goal is to solve the problem in less amount of time”
Dynamic Programming helps us in achieving this goal

How To Identify that a Problem belongs to Dynamic Programming ?

Dynamic Programming Basically a next level of Recursion, means
its an Enhanced Recursion, So if we come across a Problem which
includes inclusion and exclusion, and also there are overlapping
sub-problems in the recursive function, So we can think of a “DP” solution
and that question will belongs to a dynamic programming category

What is Mainly types of Dynamic Programming in DSA ?
1- Top-down Approach also called Memoization
2- Bottom-up Approach also known as Tabulation

Steps to solve a DP problem :
=> Define sub-problems
=> Write down the recurrence that relates sub-problems
=> Recognize and solve the base cases

Problem : Fibonacci Sequence : 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …

Recursive Function :

def fib(n): # Defines a function 'fib' that takes an integer 'n' as an argument
  if n == 1 or n == 2: #vchecks if n is equal to 1 or 2. If either condition is true, the function returns 1. 
     return 1
  return fib(n - 1) + fib(n - 2)
# fib(n - 1) recursively calls the 'fib' function with 'n - 1' as the argument.
# fib(n - 2) recursively calls the 'fib' function with 'n - 2' as the argument

DP Solution :

fib = [0] * N  # 'fib' is created, which will store the Fibonacci numbers
fib[1] = fib[2] = 1 #fib list, the values at indices 1 and 2 are set to 1.
for i in range(3, N):
    fib[i] = fib[i - 1] + fib[i - 2]

#This loop calculates the Fibonacci numbers for the rest of the sequence. 
#It starts from index 3 (since indices 1 and 2 have already been set) and goes up to index 'N - 1'

Examples of Dynamic Programming :
A few examples of “Dynamic programming”
> The 0–1 Knapsack Problem
> Chain Matrix Multiplication
> All Pairs Shortest Path
> The Floyd Warshall Algorithm: Improved All Pairs Shortest Path

Problem (leetcode) : Best Time to Buy and Sell Stock

class Solution:
    def maxProfit(self, prices):
        if not prices:
            return 0

        min_buy_price = prices[0]  # Minimum buying price encountered so far
        max_profit = 0  # Maximum profit that can be obtained
        
        for sell_price in prices:
            min_buy_price = min(min_buy_price, sell_price)  # Update the minimum buying price
            
            # Calculate the potential profit if selling at the current price
            potential_profit = sell_price - min_buy_price
            
            # Update the maximum profit if the potential profit is greater
            max_profit = max(max_profit, potential_profit)
        
        return max_profit