⭐ DYNAMIC PROGRAMMING ⭐

Dynamic Programming is mainly an optimization over plain recursion. Wherever we see a recursive solution that has repeated calls for same inputs, we can optimize it using Dynamic Programming. 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 reduces time complexities from exponential to polynomial.

---

Why Dynamic Programming

● Overlapping Subproblems
● Why calculate the answers for the subproblems again and again
● DP helps covers all possible cases

Greedy V/S DP

Greedy (one direction)

Pick k elements from a list of N elements such that their sum is maximum.

DP (try out all directions)

Pick k elements from a list of n elements such that a particular condition holds. ((f..........))
Time complexity
1. For trying out every possibility - C(n,k) => nCk (brute force)
2. With DP (break problem into sub-problems and also storing subproblems) - O(n*k) => dp[n][k]

---

Basic DP question

Find the sum of first n natural numbers. Without using the formula (N * (N + 1 )) / 2

Basic solution

int sum = 0;
for (int i = 1; i <= n; i++)
{
    sum += i;
}
cout << sum;

sum variable denotes the sum of n natural number

DP solution

int dp[n + 1];
for (int i = 1; i <= n; i++)
{
    dp[i] = i + dp[i - 1];
}
cout << dp[n];

Here, dp[i] signify sum till i

---

4 things to care about in DP problems ✨

1. State

A subproblem that we want to solve. The subproblem may be complex or easy to solve but the final aim is to solve the final problem which may be defined by a relation between the smaller sub problems (representation of a subproblem -> what does it signify)

2. Transition

Calculate the answer of state by using the answer of other smaller state (subproblems)

3. Base case

The transition expression will itself give the base case (points where the transition fails)

4. Final subproblem

Final state that the answer lies in

---

Fibonacci Number

Find the Nth Fibonacci Number where F(n) = F(n-1) + F(n-2)
F(1) = 1
F(2) = 1
F(3) = F(2) + F(1) = 2
F(4) = F(3) + F(2) = 3
F(5) = F(4) + F(3) = 5

DP Solution defining state and transition

int dp[n + 1]; // state
dp[1] = 1;
dp[2] = 1;
for (int i = 3; i <= n; i++)
{
    dp[i] = dp[i - 1] + dp[i - 2]; // transition
}
cout << dp[n] << endl; // Final subproblem

Comparing with and without DP solutions

Without DP

int functionEntered = 0;
int helper(int n)
{
    functionEntered++;
    if (n == 1 || n == 2)
        return 1;
    return helper(n - 1) + helper(n - 2);
}
void solve()
{
    int n;
    cin >> n;
    helper(n);
    cout << functionEntered << endl;
}

Here if n = 30 then
functionEntered = 1664079

With DP

int functionEntered = 0;
int dp[40];
int helper(int n)
{
    functionEntered++;
    if (n == 1 || n == 2)
        return 1;
    if (dp[n] != -1)
        return dp[n];
    return dp[n] = helper(n - 1) + helper(n - 2);
}
void solve()
{
    int n;
    cin >> n;
    for (int i = 0; i <= n; i++)
    {
        dp[i] = -1;
    }
    helper(n);
    cout << functionEntered << endl;
}

Here, if n = 30 then
functionEntered = 57