Scribd
Upload
16 views

Dynamic Programming Optimizations

Uploaded by

auiprt66
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
16 views

Dynamic Programming Optimizations

Uploaded by

auiprt66
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 22

Dynamic Programming

Optimizations

Baraa Armoush
DP Optimizations
• The main objective of Dynamic Programming is to reduce the
complexity of the program from exponential to polynomial.
• It do that dependent on the overlap of subproblems.
• But sometimes the naïve DP approach is not enough efficient.
• Top-Down version of DP can’t be improved because the values are
calculated in a random order.
• Bottom-Up version of DP can be improved because we can calculate
the values of DP in an order we specify.
DP Optimizations
• Memory Optimizations.
• Time Optimizations.
Memory Optimizations
• Rolling Table.
• Some Dimensions are Linearly connected.
• Instead of use Dp[i] as the value if we consider the i-th element and
we try to pick or leave it, we use Dp[i] as the value if we pick this
element and from it we iterative over the next element (ex: LIS).
Memory Optimizations
• Problems
• Red-Green Towers
Time Optimizations
• Prefix Sum.
• Segment Tree.
• Set or Deque.
• Matrix.
Time Optimizations – Prefix Sum
𝑗=𝑅𝑖
• 𝐷𝑝 𝑖 = 𝑗=𝐿𝑖 𝐷𝑝[ 𝑗]
• 1 ≤ 𝑖 ≤ 𝑛 , 0 ≤ 𝐿𝑖 ≤ 𝑅𝑖 < 𝑖
• The previous formula has quadratic complexity.
• If we calculate the value of Dp for each element from 1 to n, we can
compute in parallel Prefix Sum of the values of Dp.
𝑗=𝑖
• 𝑃𝑟𝑒𝑓𝑖𝑥 𝑖 = 𝐷𝑝 0 + 𝐷𝑝 1 + 𝐷𝑝 2 + ⋯ + 𝐷𝑝 𝑖 = 𝑗=0 𝐷𝑝[𝑗]
• Then the Dp formula become :
• 𝐷𝑝 𝑖 = 𝑃𝑟𝑒𝑓𝑖𝑥 𝑅𝑖 − 𝑃𝑟𝑒𝑓𝑖𝑥 𝐿𝑖 − 1
• Which has a linear complexity.
Time Optimizations – Prefix Sum
𝑘=𝑅𝑖𝑗
• 𝐷𝑝 𝑖 𝑗 = 𝑘=𝐿𝑖𝑗 𝐷𝑝 𝑖 − 1 [𝑘]
• The previous formula has cubic complexity.
• If we calculate the value of Dp for each row from 1 to n, when we
need to compute the values of Dp in the i-th row, first we can build a
prefix sum on the values of Dp in the (i – 1)-th row and the formula
become :
• 𝐷𝑝 𝑖 𝑗 = 𝑃𝑟𝑒𝑓𝑖𝑥 𝑖 − 1 𝑅𝑖𝑗 − 𝑃𝑟𝑒𝑓𝑖𝑥 𝑖 − 1 𝐿𝑖𝑗 − 1
• Which has a quadratic complexity.
• The same idea is correct if we have more than two dimensions.
Time Optimizations – Prefix Sum
• Problems
• Candies
• Riding in a Lift
• New Year and Ancient Prophecy
• Vasya and Array
Time Optimizations – Segment Tree
• 𝐷𝑝 𝑖 = min 𝐷𝑝 𝑗
𝐿𝑖 ≤𝑗≤𝑅𝑖
• 1 ≤ 𝑖 ≤ 𝑛 , 0 ≤ 𝐿𝑖 ≤ 𝑅𝑖 < 𝑖
• The previous formula has quadratic complexity.
• If we calculate the value of Dp for each element from 1 to n, we can
compute in parallel Minimum Segment Tree of the values of Dp.
• Then the Dp formula become :
• 𝐷𝑝 𝑖 = 𝑆𝑒𝑔𝑚𝑒𝑛𝑡𝑇𝑟𝑒𝑒. 𝑄𝑢𝑒𝑟𝑦𝑀𝑖𝑛(𝐿𝑖 , 𝑅𝑖 )
• Which has a complexity 𝑂(𝑛 ∗ log 𝑛 ).
• The same idea is correct if we have more dimensions.
Time Optimizations – Segment Tree
• Example
• Longest Increasing Subsequence.
• Problems
• Flowers
• Babaei and Birthday Cake
• Hanoi Factory
Time Optimizations – Lazy Segment Tree
• 𝐷𝑝 𝑖 = min (𝐶𝑜𝑠𝑡 𝑖, 𝑗 + 𝐷𝑝 𝑗 )
𝐿𝑖 ≤𝑗≤𝑅𝑖
• 1 ≤ 𝑖 ≤ 𝑛 , 0 ≤ 𝐿𝑖 ≤ 𝑅𝑖 < 𝑖
• Some formulas can be improved using Lazy Segment Tree (depended
on the function Cost ).
• Problems
• The Bakery
• Intervals
• Animal Observation (hard version)
Time Optimizations – Set or Deque
• 𝐷𝑝 𝑖 = min 𝐷𝑝 𝑗
𝐿𝑖 ≤𝑗≤𝑅𝑖
• 1 ≤ 𝑖 ≤ 𝑛 , 0 ≤ 𝐿𝑖 ≤ 𝑅𝑖 < 𝑖 , 𝑳𝒊 ≤ 𝑳𝒊+𝟏 , 𝑹𝒊 ≤ 𝑹𝒊+𝟏
• The previous formula has quadratic complexity.
• The ranges 𝐿𝑖 , 𝑅𝑖 form a sliding window.
• We can use set or deque to know the minimum value in the window at
any point of time.
• Set complexity : 𝑂 𝑛 ∗ log 𝑛
• Deque complexity : 𝑂 𝑛
Time Optimizations – Set or Deque
• Problems
• Cashback
• Strip
• Pictures with Kittens
• Bowling for Numbers++
Time Optimizations – Matrix
𝑗=𝑘
• 𝐷𝑝 𝑖 = 𝑗=1 𝑎𝑗 ∗ 𝐷𝑝[𝑖 − 𝑗]
• 𝐷𝑝 𝑖 = 𝑎1 ∗ 𝐷𝑝 𝑖 − 1 + 𝑎2 ∗ 𝐷𝑝 𝑖 − 2 + ⋯ + 𝑎𝑘 ∗ 𝐷𝑝[𝑖 − 𝑘]
•𝑘≤𝑖≤𝑛
• The previous formula has complexity 𝑂 𝑛 ∗ 𝑘
Time Optimizations – Matrix
•𝑘=3
0 0 𝑎3
𝐷𝑝0 𝐷𝑝1 𝐷𝑝2 ∗ 1 0 𝑎2
0 1 𝑎1

= 𝐷𝑝1 𝐷𝑝2 (𝑎1 ∗ 𝐷𝑝2 + 𝑎2 ∗ 𝐷𝑝1 + 𝑎3 ∗ 𝐷𝑝0 )

= 𝐷𝑝1 𝐷𝑝2 𝐷𝑝3


Time Optimizations – Matrix
•𝑘=3
0 0 𝑎3
𝐷𝑝1 𝐷𝑝2 𝐷𝑝3 ∗ 1 0 𝑎2
0 1 𝑎1

= 𝐷𝑝2 𝐷𝑝3 (𝑎1 ∗ 𝐷𝑝3 + 𝑎2 ∗ 𝐷𝑝2 + 𝑎3 ∗ 𝐷𝑝1 )

= 𝐷𝑝2 𝐷𝑝3 𝐷𝑝4


Time Optimizations – Matrix
•𝑘=3
0 0 𝑎3
𝐷𝑝1 𝐷𝑝2 𝐷𝑝3 ∗ 1 0 𝑎2
0 1 𝑎1

0 0 𝑎3 0 0 𝑎3
= 𝐷𝑝0 𝐷𝑝1 𝐷𝑝2 ∗ 1 0 𝑎2 ∗ 1 0 𝑎2
0 1 𝑎1 0 1 𝑎1

= 𝐷𝑝2 𝐷𝑝3 𝐷𝑝4


Time Optimizations – Matrix
•𝑘=3 𝑛
0 0 𝑎3
𝐷𝑝0 𝐷𝑝1 𝐷𝑝2 ∗ 1 0 𝑎2
0 1 𝑎1

= 𝐷𝑝𝑛 𝐷𝑝𝑛+1 𝐷𝑝𝑛+2


Time Optimizations – Matrix
• In General ⋯ 𝑛
0 0 0 0 𝑎𝑘
1 0 ⋯ 0 0 𝑎𝑘−1
⋯ 𝑎𝑘−2
𝐷𝑝0 𝐷𝑝1 … 𝐷𝑝𝑘−1 ∗ 0 1 0 0
⋮ ⋮ ⋱ ⋮ ⋮ ⋮
0 0 ⋯ 1 0 𝑎2
0 0 ⋯ 0 1 𝑎1

= 𝐷𝑝𝑛 𝐷𝑝𝑛+1 … 𝐷𝑝𝑛+𝑘−1


• Complexity 𝑂(𝑘 3 ∗ log 𝑛 )
Time Optimizations – Matrix
• Problems • Problems
• Magic Gems • Darth Vader and Tree
• Walk • Sonya and Informatics
• RGB plants • Wet Shark and Blocks
• Apple Trees • Product Oriented Recurrence
• Xor-sequences • Dexterina’s Lab
• GukiZ and Binary Operations • Okabe and El Psy Kongroo
• PLEASE
To Be Continued

You might also like