Dynamic Programming21 sections · 916 units
Open in Course

Quiz: Linear Form Recognition

Identifying CHT applicability

Check Your Understanding

CHT applies when DP recurrence is dp[i] = min_j(m[j] * x[i] + b[j]) + c[i]. What must be true?

  1. A.The values m[j] must all be positive
  2. B.The values x[i] must be sorted in decreasing order
  3. C.The term involving j and i must be separable as m[j] * x[i]
  4. D.The cost function must satisfy quadrangle inequality
Start the roadmap to answer the quizzes and solve the challenges