0% found this document useful (0 votes)
272 viewsDynamic Programming - From Novice To Advanced - Topcoder
Dynamic Programming – From Novice to Advanced – Topcoder
Uploaded by
AnushiMaheshwariCopyright
© © All Rights Reserved
Available Formats
Download as PDF or read online on Scribd
0% found this document useful (0 votes)
272 viewsDynamic Programming - From Novice To Advanced - Topcoder
Dynamic Programming – From Novice to Advanced – Topcoder
Uploaded by
AnushiMaheshwariCopyright
© © All Rights Reserved
Available Formats
Download as PDF or read online on Scribd
/ 11
e220%6
Dynamic Programming -From Novice te Advances —topcoder
MENU
(i
1) Anushi
EDIT
DASHBOARD
MY PROFILE
PAYMENTS
SETTINGS
Loc ouT
COMPETE
DESIGN CHALLENGES
DEVELOPMENT CHALLENGES
DATA SCIENCE CHALL
Ices
COMPETITIVE PROGRAMMING
LEARN
GETTING STARTED
DESIGN
DEVELOPMENT
DATA SCIENCE
telpeuhwwntapcodercom/commurity/dala-scienceldata-science-tAaralldyramic-programming from-navice-o-advanced
wm e220%6 Dynamic Programming -From Novice te Advances —topcoder
COMPETITIVE PROGRAMMING
COMMUNITY
overview
PROGRAMS
FORUMS
sTatistics
EVENTS
BLOG
Dynamic Programming - From Novice to Advanced
By Dumitru —topcoder member
Discuss this article in the forums
‘An important part of given problems can be solved with the help of dynarnic programming (DP for short) Being able to tackle
problems of this type would greatly increase your skill. | will try to help you in understanding how to solve problems using DP.
The article is based on examples, because a raw theory is very hard to understand,
Note: f you're bored reading one section and you already know what's being discussed in it - skip it and go to the next one.
Introduction (Beginner)
What is a dynamic programming, how can it be described?
ADPis an algorithmic technique whichis usually based on a recurrent formula and one {or some} starting states, A sub-solution
ofthe problem is constructed from previously found ones, DP solutions have a polynomial complexity which assures @ much
faster running time than other techniques like backtracking, brute-force etc.
Now let’s see the base of DP with the help of an example:
telpeuhwwntapcodercom/commurity/dala-scienceldata-science-tAaralldyramic-programming from-navice-o-advanced ant saint Dyna Programming Fram Novice to Aavercea opcode
Given a lst ofN coins, their values (Vy, Vg, ..., Wy, 2nd the total sum S, Find the minimum number of coins the sum of which is $
(we can use 2s many coins of one type as we want}, or report that it's not possible to select coins in such a way that they sum up
to,
Now let's start constructing a DP solution:
First of all we need to find a state for which an optimal solution is found and with the help of which we can find the optimal
solution for the next state.
What does a "state" stand for?
Its away to describe a situation, a sub-solution for the problem, For example a state would be the solution for sum i, where #SS,
Asmaller state than state
states j (isi
ina.
would be the solution for any sum j, where jel. For finding a state i, we need to first find all smaller
Having found the minimum number of coins which sum up toi, we can easily find the next state - the solution for
How can we find it?
Itis simple -for each cain j, Wisi look 2t the minimum number of coins found for the F-Vjsum (we have already found it
previously) Let this number dem. ffm#d is less than the minimum number of coins already found for current sum i, then we
write the new result fort
For a better understanding let's take this example:
Given coins with values 1, 3, and.
And the sum Sis set to be 11
First ofall we mark that for state 0 (sum 0] we have found a solution with 2 minimum number of 0 coins. We then go to sum 1
First, we mark that we haven't yet found a solution for this one (a value of Infinity would be fine). Then we see that only coin Lis
less than or equal to the current sum, Analyzing it, we see that for surn 1-V,= 0 we have a solution with 0 coins, Because we add
one coin to this solution, we'll have a solution with 1 coin for sum 2. Its the only solution yet found for this sum, We write (save)
it. Then we proceed to the next state sum 2. We again see that the only coin which is less or equal to this sum is the first coin,
having a value of 1. The optimal solution found for sur (2-1) Lis coin 1. This coin 2 plus the frst coin will sum up to2, and thus
make a sum of 2 with the help of only 2 coins, Thisis the best and only solution for surn 2. Now we proceed to sum 3, We no
have 2 coins which are to be analyzed ~ first end second one, having values of 1 and 3, Let’s see the first one. There exists a
solution for sum 2 (3 1) and therefore we can construct from ita solution for sum 3 by adding the first coin tot. Because the
best solution for sum 2 that we found has 2 coins, the new solution for sur 3 will have 3 coins, Now let's take the second coin
with value equal to 3. The sum for which this coin needs to be added to make 3, is 0. We know that sum is made up of 8 coins.
Thus we can make a sum of 3 with only one coin ~3. We see that it's better than the previous found solution for sum 3, which
‘was composed of 3 coins. We update it and mark it as having only 1 coin, The same we do for sum 4, and get a solution of 2 coins
= 143. And so on.
Pseudocode:
Set Min[i] equal to Infinity for all of i
telpeuhwwntapcodercomicommurity/dala-sciencaldala-sience-tAaralldyramic-programming from-navice-o-advanced ant e220%6 Dynamic Programming -From Novice te Advances —topcoder
mine:
For i=1tos
For j=@toN-2
Tf (Vjcei AND Min[i-Vj]+1
9 13
w 2
n 3
Coin value added to @ smaller sum to
obtain this sum (tis displayed in brackets)
10)
10)
3(0)
18)
50)
303)
1(6)
315)
18)
515)
120}
‘Asa result we have found a solution of 3 coins which sum up to 11.
Additionally, by tracking data about how we got to a certain sum from a previous one, we can find what coins were used in
buildingit. For exernple: to sum 11 we got by adding the coin with value 1 to a sum of 10. To surn 10 we got from 5. To 5—from 0
This way we find the coins used: 1, 5 and 5.
Having understood the basic way a DP is used, we may now see a slightly different approzc” to it. tinvolves the change
(update) of best solution yet found for a sum i whenever a better solution for this sum was found. In this case the states aren’t
calculated consecutively. Let’s consider the problem above. Start with having a solution of @ coins for sum 0. Now let's try to add
first coin (with value 1} to all surns already found. fthe
resulting sum t will be composed of fewer coins than the one previously
found - welll update the solution fort. Then we do the same thing for the second coin, third coin, and so on for the rest of them.
For example, we first add coin 1 to sum 0 and get sum 1. Because we haven't yet found a possible way to rake a surn of l- this,
telpeuhwwntapcodercom/commurity/dala-scienceldata-science-tAaralldyramic-programming from-navice-o-advanced ant e220%6 Dynamic Programming -From Novice te Advances —topcoder
And
isthe best solution yet found, and we mark S[AJ=2. 8y adding the same coin to sum 1, we'll get sum 2, thus making S[2]=
s0 on for the first coin. After the first coin is processed, take coin 2 (having a value of 3) and consecutively try to add it to each of
the sums already found. Adding it to 0, a sum 3 made up of 1 coin will result, Till now, S{3] has been equal to 3, thus the new
Atter adding the same coin to sum 1, we'll get a
sum 4 composed of coins. Previously we found a sum of 4 composed of 4 coins; having now found a better solution we update
solution is better than the previousiy found one, We update it and mark $[3]=I
S[4] to 2, The same thing is done for next sums - each time a better solution is found, the results are updated
Elementary
To this point, very simple examples have been discussed. Now let's see how to find a way for passing from one state to another,
forharder problems. For that we will introduce a new term celled recurrent relation, which makes @ connection between a lower
anda greater state
Lets see how it works:
Given a sequence of N numbers ALA], AL2I, .., AIN] .Find the length of the longest non-decreasing sequence.
As described above we must first find how to define a “state” which represents a sub-problem and thus we have to find 2
solution forit, Note that in most cases the states rely on lower states and are independent from greater states,
Lets define
te as being the longest non-decreasing sequence which has its last number Ali]. This state carries only data
about the length of this sequence, Note that for Ij the statel is independent from , ie. doesn’t change when we calculate state
J. Le’s see now how these states are connected to each other. Having found the solutions forall states lower than I, we may now
look for statet. At frst we initialize it with a solution of 1, which consists only ofthe i-th number "self. Now for each je let's see if
it's possible to pass from it to state i This s possible only when ALISA, thus keeping (assuring) the sequence non-decreasing.
So if Sj] {the solution found for state) +2 (number Afi] added to this sequence which ends with number Alj} is better than a
solution found fori (ie. S[j]#4>S[i] }, we make S[i]=S[j}+2. This wey we consecutively find the best solutions for each i, until fast
staten.
Let's see what happens fora randomly generated sequence: 5, 3, 4,8, 6,7
‘The length ofthe longest |The last sequence i from
non-decreasing sequence which
of sti nurnbers tothisone
"arrived"
1 1 1 first number itself)
2 1 2 (second number itself)
3 2 2
4 3 3
5 3 3
6 4 5
telpeuhwwntapcodercom/commurity/dala-scienceldata-science-tAaralldyramic-programming from-navice-o-advanced sit e220%6 Dynamic Programming -From Novice te Advances —topcoder
Practice problem:
Given an undirected graph G having N (1«N==1000} vertices and positive weights. Find the shortest path from vertex 1 to vertex:
N, or state that such path doesn’t exist
Hint: At each step, among the vertices which weren't yet checked and for which a path from vertex 1 was found, take the one
which has the shortest path, from vertex 1 tot, yet found
Try to solve the follow
1g problems from topcoder competitions:
Zigzag - 2008 TCCC Semifinals 3
BadNeighbors - 2004 TCCC Round 4
FlowerGarden - 2004 TCCC Round 1
Intermediate
Let's see now how to tackle bi-dimensional DP problems
Problem:
table composed of NxM cells, each having a certain quantity of apples, is given. You start from the upper-left corner. At each
step you can go down or right one cell. Find the maximum number of apples you can collect.
This problem is solved in the same way as other DP problems; there is almost no differenc
First of all we have to find a state, The first thing that must be observed is thet there are at most 2 ways we can come to a cell -
from the left ifit’s not situated on the first column) and from the top [ifit’s not situated on the most upper row). Thus to find the
best solution for that cell, we have to have already found the best solutions forall of the cells frorn which we can arrive to the
current cell
From above, # recurrent relation can be easily obtained
‘S[i]LJ]=ALi]L[j] + max(S[i-1][j], if i>0 5 S[i][j-1], if j>0) (where i represents the row and j the column of the table, its left-upper
corer having coordinates (0,0; ene ALL] deing the number of apples situated in cel gh.
[ij] must be calculated by going first from left to right in each row and process the rows from top to bottom, ar by going frst
fror top to bottom in each column and process the colurnns from left to right
Pseudocode:
For i=@toN-1
For j=@tom-1
S(i][5] = ACA](5] +
max(S[i][J-1], if j>® ; S[i-1][J], if ie 5 @)
telpeuhwwntapcodercomicommurity/dala-sciencaldala-sience-tAaralldyramic-programming from-navice-o-advanced ant e220%6 Dynamic Programming -From Novice te Advances —topcoder
Output S[n-1][m-1]
Here are a few problems, from topcoder Competitions, for practicing:
AvoidRoads ~ 2003 TCO Semifinals 4
ChessMetric - 2003 TCC Round 4
Upper-Intermediate
This section will discuss about dealing DP problems which have an additional condition besides the values that must be
calculated
‘As @ go0d example would serve the following problem:
Given an undirected graph G having positive weights and N vertices
You start with having a sum of M money. For passing through a vertex, you must pay Sli] money. Ifyou don’t have enough
money you can't pass through that vertex. Find the shortest path from vertex to vertex N, respecting the above conditions; or
state that such path doesn't exist. f there exist more than one path having the same length, then output the cheapest one.
Restrictions: 1-@ AND
Min{p][1-SEp] ]>Min[k] [1]+Dist[k][p])
Then Min{p]{1-Slp]]=Minfk][1]+0ist{k] [p]
ie.
If for state(i,j) there are enough money left for
going to vertex p (1-S[p] represents the money that
will remain after passing to vertex p), and the
shortest path found for state(p,1-S[p]) is bigger
than [the shortest path found for
state(k,1)] + [distance from vertex k to vertex p)],
then set the shortest path for state(i,j) to be equal
to this sun.
End For
End While
Find the smallest number among Min[N-1][j] (for all j, @<=j<=M);
if there are more than one such states, then take the one with greater
J. If there are no states(N-1,j) with value less than Infinity - then
such a path doesn't exist.
‘
Here area few TC problems for practicing:
Jewelry: ‘CO Online Round 4
StripePainter- SRM 150 Div 1
QuickSums - SRM 197 Div2
ShortPalindromes -
SRM 165 Div2
Advanced
telpeuhwwntapcodercom/commurity/dala-scienceldata-science-tAaralldyramic-programming from-navice-o-advanced
ant e220%6 Dynamic Programming -From Novice te Advances —topcoder
The following problems will need some good observations in order to reduce them to a dynamic solution,
Problem StarAdventure - SRM 208 Div 1:
Given a matrix with M rows and N columns (NxM). In each cell there's a number of apples.
You start rom the upper-left corner of the matrix. You can go down or right one cell. You need to arrive to the bottom-right
commer. Then you need to go back to the upper-left cell by going each step one cell left or up. Having arrived at this upper-left cell,
you need to go again back to the bottom-right cell
Find the maximum number of apples you can collect.
When you pass through a cel - you collectall the apples left there,
Restrictions: 1