DYNAMIC PROGRAMMING

LECTURE

Dynamic Programming : a very powerful method for solving a

complex problem by breaking it down into a collection of simpler
subproblems, solving each of those subproblems just once, and
storing their solutions/results.
There are two ways of doing this.

1.) Top-Down : Start solving the given problem by breaking it down. If you
see that the problem has been solved already, then just return the saved
answer. If it has not been solved, solve it and save the answer. This is
usually easy to think of and very intuitive. This is referred to as
Memoization. (We will go from higher states towards lower states).

2.) Bottom-Up : Analyze the problem and see the order in which the
sub-problems are solved and start solving from the trivial subproblem, up
towards the given problem. In this process, it is guaranteed that the
subproblems are solved before solving the problem. This is the Iterative
Approach. (We will go from lower states towards higher states).
 Types of problems that can be solved using Dp/Motivation
behind studying the topic :

● If the problems asks us to minimize/maximize something or asks us to

find the # of ways of doing something , then dp might be applicable.

● If you are able to form a recurrence relation.

● If a greedy approach isn't working, then dp might just work.

Let’s take an example of finding the nth fibonacci term.

1) Method 1: (Recursive Solution)

Just naively writing down a recursive function :

Top down approach but without memoization:

int fibo_simple(int x) {
if (x <= 2)return 1;
return fibo_simple(x - 1) + fibo_simple(x - 2);
}

Problem with above approach :

For n=7, fibo(5) being calculated twice , fibo(4) being calculated thrice and so
on……

Time complexity : T(n) = T(n-1) + T(n-2)

So to calculate the nth term, we will spend fibo(n) time.

(very inefficient since the fibonacci series grows pretty fast.)

Recursive solution (but with memoization) :

int dp[N]; // initialize with some garbage value. (garb_val)

int fibo_with_memo(int x) {

if (dp[x] != garb_val)return dp[x];

// since we already know it’s value.

if (x <= 2) {
dp[x] = 1;
}
else {
dp[x] = fibo_with_memo(x - 1) +
fibo_with_memo(x - 2);
}

return dp[x];
}

Time complexity : O(n) Linear !!

Saving/Storing the result saved us a lot of time and computation.

Above was the example of Top down Dp/Memoization.

Let’s look at the bottom up/iterative approach

int n;
cin>>n;
int fibo[n+1];

fibo[1] = 1, fibo[2] = 1;
 for (int i = 3; i<= n; i++) {
fibo[i] = fibo[i - 1] + fibo[i - 2];
}

● The way you define your dp is super important.

In the above case, fibo[i] denotes the i’th term of the fibonacci series
which seems very trivial and obvious but it is not always the case.

Problem: Find the number of different binary sequences of length N

such that no 2 1’s are adjacent to each other.
Solution :

Let dp[i] denotes the no. of such sequences of length i.

Now,consider a sequence of length i.

2 cases :

● ith element is 0. In this case (i-1)th element can be 0 or 1. So # of

ways will be dp[i-1]

[…………] 0

● ith element is 1. (i-1)th element must be 0. Then, (i-2)th element can

either be 1 or 0.
So # of ways will be dp[i-2]

.…………...1

[………] 01
Hence we get the relation :

dp[i] =dp[i-1] +dp[i-2].

Some Standard Dp Problems :

(will help you understand different ways in which we may
define our dp)

● 0-1 Knapsack
● Longest Increasing Sequence (LIS)
● Coin change Problem
● Longest common subsequence (LCS)
● LIS (in nlogn)
● Solving recursive relations for large n (order of
1e9,1e18) using matrix exponentiation

● Longest Increasing Subsequence

Problem: Given an array A of length n, find the length of the longest
increasing subsequence of A.

Example-
N=7
A=[2,1,8,5,3,6,9]
1,3,6,9
Ans=4

Solution :
Let dp[i] denote the length of Longest Increasing Subsequence ending
at i.
Then for every i in 1 to n,we see every j from 1 to i-1. If arr[i]>arr[j],
then arr[i] is a possible contender for the last element of the LIS and
we can include arr[i] in the LIS ending at j. We take the maximum of
all the values of dp[i] to get the answer.(This is because LIS can end at
any index and not necessarily n)

Code: (O(N*N) implementation)

cin >> n;
int arr[n+1];
for(i=1;i<=n;i++)
cin>>arr[i];
int dp[n+1];
//dp[i] denotes length of LIS ending at i
for(i=1;i<=n;i++)
{
dp[i]=1;
 for(j=1;j<=(i-1);j++)
{
if(arr[i]>arr[j])
{
dp[i]=std::max(dp[i],dp[j]+1);

//Taking maximum as we want largest possible

//length of LIS ending at i
}
}
ans=std::max(ans,dp[i]);

}
cout<<ans;

Time complexity : O(N*N)

Space complexity : O(N)

For NlogN implementation -

https://www.geeksforgeeks.org/longest-monotonically-increasing-subs
equence-size-n-log-n/

Practice Task -
https://codeforces.com/problemset/problem/269/B
(Try to implement in NlogN as well)

Extra Task-

Try to print the Longest Increasing Subsequence

0-1 Knapsack Problem

Problem: There are N items ,each of them having some weight w[i]
and value v[i] associated with them.You also have a knapsack with
capacity S.
You need to put a subset of items in the Knapsack such that their total
weight
does not exceed S and their total value is Maximized.

You cannot break an item i.e either pick it completely or don’t pick it.
(Hence the name 0-1 Knapsack).

One of the possible approaches:

● Sort the items in decreasing order of value/weight ratio and then

pick the items greedily.

However,this approach fails for:

item weight value value/weight

A 5 4 0.8

B 4 3 0.6

C 4 2 0.5

Knapsack capacity,S = 8.

Optimal answer is 3+2 =5 (pick B and C).

Hence,the above greedy approach is NOT correct.

[Note: This approach works if we can break an item.(fractional

knapsack)]

Solution using Dp:

Let’s try to solve a simpler version of this problem.

What if you just need to tell what is the maximum weight <=S that you can
achieve by choosing a subset of the items.

Let us make a 2D boolean array ‘dp’ in which dp[i][j] is 1 if it is possible to make

weight =‘j’ from the first ‘i’ items.
Else dp[i][j] is 0.
Dp[i][j] ---> Dp[i-1][j] ,we didn’t choose the ith item.

Dp[i][j] ---> Dp[i-1][j-w[i]] , we chose the ith item.

If atleast one of the states is 1, then dp[i][j] will be 1.

Example:

item weight

A 1

B 3

Total 0 1 2 3 4
Weight

{} 1 0 0 0 0

{1} 1 1 0 0 0

{1,3} 1 1 0 1 1

In the end, simply report the maximum ‘x’ <=S such that, dp[n][x] =1.

int n, S;

cin >> n >> S;

bool dp[n+1][S+1];
memset(dp,0,sizeof(dp));

int w[n+1];

for (int i = 1; i <= n; i++)cin >> w[i];

dp[0][0] = 1; // important line.

for (int i = 1; i <= n; i++) {

for (int j = 0; j <= S; j++) {
dp[i][j] |= dp[i - 1][j];
if (j >= w[i]) {
dp[i][j] |= dp[i - 1][j - w[i]];
}
}
}

for (int x = S; x >= 0; x--) {

if (dp[n][x]) {
cout << x << endl;
return 0;
}
}

Time complexity : O(N*S)

Space complexity : O(N*S)

So if N*S <=1e7-1e8 then do consider knapsack.

[Note: XeY means X*(10^Y)]

Now let’s come back to our original problem:

Let dp[i][j] denote the maximum value that we can get from first ‘i’
items and for a total weight ‘j’.

Dp[i][j] --> Dp[i-1][j] (Don’t pick the ith item)

Dp[i][j] ----> Dp[i-1][j-w[i]] + v[i] (pick it)

int n, S;

cin >> n >> S;

int inf = 1e9;

int dp[n + 1][S + 1];

for (int i = 0; i <= n; i++) {

for (int j = 0; j <= S; j++)dp[i][j] = -inf;
}

dp[0][0] = 0;

int w[n + 1];

int v[n + 1];

for (int i = 1; i <= n; i++)cin >> w[i] >> v[i];

for (int i = 1; i <= n; i++) {
for (int j = 0; j <= S; j++) {

dp[i][j] = max(dp[i][j], dp[i - 1][j]);

if (j >= w[i]) {
dp[i][j] = max(dp[i][j], dp[i - 1][j - w[i]] + v[i]);
}

}
}

int answer = 0;

for (int x = S; x >= 0; x--) {

answer = max(answer, dp[n][x]);
}

cout << answer << endl;

● Coin Change Problem:

Problem: You have an infinite supply of n coins with values
V1,V2,....Vn resp. and a target sum ‘S’.
Find the number of ways to make sum S. (order doesn’t
matter i.e
For S=4 and V={1,2,5}, [1 1 2] is same as [1 2 1] )

Solution : Let f[i][j] denote the no. of ways to get sum j using first i
coins only.

Let the value of ith coin be x (i.e v[i] =x)

Then f[i][j] = f[i-1][j] + f[i-1][j-x] +f[i-1][j-2*x]..........

 Note: f[i-1][j-m*x] denotes that we have chosen i’th coin exactly m
times.

● i’th row denotes that we are considering only first i coins.

● j’th column denotes that the sum=j.

F[i][j] : Value in the i’th row and j’th column.

Sum 0 1 2 3 4 5 6 7 8 9 10
{} 1 0 0 0 0 0 0 0 0 0 0
{1} 1 1 1 1 1 1 1 1 1 1 1
{1,2} 1 1 2 2 3 3 4 4 5 5 6
{1,2,5} 1 1 2 2 3 4 5 6 7 8 10

Time complexity : bigger than O(n*m)

Reason: for v[i] =x , f[i][j] takes “some” time to compute and there
are total n*m states.

Let’s try to compute f[i][j] in O(1).

f[i][j] = f[i-1][j] + f[i-1][j-x] +f[i-1][j-2*x].......... (1)

Putting j=j-x in (1),

f[i][j-x] = f[i-1][j-x] +f[i-1][j-2*x]+f[i-1][j-3*x]....... (2)

So from (1) and (2),

f[i][j] = f[i-1][j] +f[i][j-x]

Where x= V[i]

Time complexity and Space complexity O(N*M)

HW PROBLEM:

Find the minimum number of coins to make a given value/sum S.

● Longest Common Subsequence

Given two strings S1 and S2 of size n and m respectively, find the

length of their Longest Common Subsequence(LCS)

Example -
45
KXBY
ACXCY

Answer =2
(XY)

Solution:

Let dp[i][j] denote length of Longest Common subsequence such that

we consider first i characters of s1 and j characters of s2.Thus, the
answer will be dp[n][m]. When i or j is 0, dp[i][j] will be 0. When
characters at ith position of s1 and jth position of s2 are same(Here
s1[i-1] and s2[j-1] due to 0-based indexing), we can include them in
the LCS and dp[i][j]=1+dp[i-1][j-1]. If characters are different , we
cannot include them in the LCS.So, dp[i][j] will be the maximum of
dp[i-1][j](When we don't consider ith character of s1) and
dp[i][j-1].(When we don't consider jth character of s2)

Code:
cin >> n >> m;
cin>>s1>>s2;
int dp[n+1][m+1];
//dp[i][j] denotes length of Longest Common Subsequence
//when we consider first i characters of s1 and j characters
//of s2
 for(i=0;i<=n;i++)
{
for(j=0;j<=m;j++)
{
if((i==0)||(j==0))
{
dp[i][j]=0;
}
else
{
if(s1[i-1]==s2[j-1])
dp[i][j]=1+dp[i-1][j-1];
else
{
dp[i][j]=std::max(dp[i-1][j],dp[i][j-1]);
}
}

}
}
int ans=dp[n][m];
cout<<ans;

Time complexity : O(N*M)

Space complexity : O(N*M)

Practice Task :
https://cses.fi/problemset/task/1639

Extra Task:
Try to print the LCS of 2 strings.
Resources:
1) Intuition Behind Dp
2) Knapsack
3) Coin Change
4) LIS/LCS
5) LIS in nlogn
6) BitMask Dp
7) Matrix Exponentiation
8) Longest Common Subsequence (Visualisation)

Contests/Problemset for practice :

1) AtCoder Educational DP (highly recommended)
2) CSES (highly recommended)
3) Codechef DSA Dp

Problems for practice :

1) Lecture Sleep
2) Mashmokh and ACM
3) Orac and Models
4) XOR with Subset
5) Find the Spruce
6) Dessert Wizard
7) Maximum Sum of Products
8) Baby Ehab Partitions Again
9) Good Subarrays
10) Almost Identity Permutations
11) Booking System
12) Bargain
13) Buns
14) Treats for the Cows
15) Buses
16) Mysterious Present
17) Ilya and Escalator
18) Multiple of 2019
19) The Empty One
20) Caesar's Legion
21) Wonderful Randomized Sum
22) Flowers
23) Maximum Score
24) Kefa and Dishes
25) Fish
26) Let's Go Rolling
27) LionAge II
28) Longest Regular Bracket Sequence
29) Shooting Gallery
30) Education Reform
31) Two out of Three
32) Traveler
33) Petr#
34) The least round way
35) Checkout assistant
36) Looking for Order
37) Petya and spiders
38) Games with rectangles
39) Pawn
40) Comb
41) Big Maximum sum
42) Knapsack for All Segments
43) Dot
44) First Digit Law
45) Roman and Numbers
46) Sequence
47) A Simple Task
48) Stripe 2
49) Number with the given amount of Divisors
50) Brackets