Dynamic Programming21 sections · 916 units
Open in Course

Quiz: Quadrangle Inequality

Testing the concept

Check Your Understanding

A cost function satisfies quadrangle inequality if for i <= j <= k <= l, cost(i,l) + cost(j,k) >= cost(i,k) + cost(j,l). What does this mean intuitively?

  1. A.Crossing intervals have higher total cost than nested intervals
  2. B.Overlapping intervals can be merged without cost increase
  3. C.Smaller intervals are always cheaper
  4. D.The cost function is always convex
Start the roadmap to answer the quizzes and solve the challenges