DP-Dynamic Programming

Atcoder Educational DP contest Editorial

#define DP DynamicProgramming
#define nD nth Dimension DP

preRequisites:-

1. Recursion

https://img.devrant.com/devrant/rant/r_2210586_WFd3W.jpg

2. A programming language, c++ preferable

Why Atcoder for DP ?

A curated list of DP specific problems that covers all the concepts in DP

How should I know that the problem is DP?

Well, that’s simple I’ll tell you how I do that and a general way

myWay:-

1. You have decision-making way too often where greedy fails to give the minimum/maximum answer or you see terms like shortest/longest, minimized/maximized, least/most, fewest/greatest, biggest/smallest,
2. Find the total number of solutions possible

Now that I told my way let’s look at the general way

generalWay:-

https://pics.me.me/when-you-are-learning-about-dynamic-programming-modern-solutions-require-39682345.png

DP is essentially just an optimization technique.
The statement should satisfy the principle of optimality

1. overlapping subproblem
2. optimal substructure

How do I know whether it’s 1D DP or nD DP where n>1?

Its simple guy's no of the states you have in your recursive approach is the key to dimensions.

A — Frog 1

Problem Statement

Find the minimum possible total cost incurred before the frog reaches Stone N.

The frog should make a decision at every jump, from stone i it should jump to either i+1 or i+2 , so try using greedy where it has no decision making capability you might get away with a minimal answer but not the minimum possible answer

A - Frog 1

Recurrence Relation:-

I am not talking about Recursion assuming you know that.

Before we head to the relation let’s define the states. We are only tracking the current position of the frog so the position is the only state we have.

Select the path that cost’s less so find out the minimum of the two
i+1 or i+2 and make the move to that step.

calc is the recursive function with parameter pos position.
C is the cost array where ci is the cost of stone i .
min(calc(pos+1)+abs(C[pos]-C[pos+1]),calc(pos+2)+abs(C[pos]-C[pos+2]))

Now we have got the relation how should we memorize it so it won’t take a time complexity of O(2^n) . Here’s a noob tip try to store the state somehow.
So, for every, pos we are going to store the min possible in the vector dp .

Now we have a DP solution to the problem.

Code:-

We have three things with us

1. States
2. Base condition
3. Recurrence Relation

Now we can use the Recurrence relation to write an iterative solution as follows.

B — Frog 2

Find the minimum possible total cost incurred before the frog reaches Stone N.

B - Frog 2

Recurrence Relation:-

This one is the same as the above question but here the frog has way many decisions to be made. The frog can make a jump to almost k position from pos position.

So, we have to check for all the possible steps and memorize the min at each state/pos

Code:-

The below one is the iterative DP for the problem if you could write the iterative DP for FROG-I then this is easy to understand.

C — Vacation

Find the maximum possible total points of happiness that Taro gains.

C - Vacation

Recurrence Relation:-

This one is like a scheduling algorithm where we are going to explore all the possible patterns of selection and memorize the best one.

li is the 2D vector-matrix which would store the input in the format given.

States:-
n every day we have to remember what he has done
pos What did Taro do on the nth day

We have two states to track so we are going to have 2D memorization here.

Our recursive solution would take time-complexity of O(3^n). Guess the time complexity after applying DP .

Code:-

Now let’s look into the iterative approach.

So, after converting it into iterative DP this is what I got

Now the complete code is

D — Knapsack

Find the maximum possible sum of the values of items that Taro takes home.

D - Knapsack 1

Recurrence Relation:-

Hmm, In this question we have the choice to pick an item or not depending on its weight and availability. Since we are deciding on two parameters we have two states.

items is the 2D vector-matrix which would store the input in the format given.

States:-
i item.
w the weight that a knapsack can hold.

We have two states to track so we are going to have 2D memorization here.

Our recursive solution would take time-complexity of O(2^n). Guess the time complexity after applying DP .

Let’s have a look at the recurrence relation.

Code:-

The above code is Recursion Let’s have a peek into iterative DP.

G — Longest Path

Find the length of the longest directed path in G. Here, the length of a directed path is the number of edges in it.

D — Knapsack 1

Recurrence Relation:-

Any basic graph traversal will do the trick guys.

States:-
n node.