Convex Hull Trick (CHT) DP Optimization Interactive Visualizer
The Convex Hull Trick optimizes DP recurrences of the form dp[i] = min_j(m_j * x_i + c_j) from O(n^2) to O(n) or O(n log n) by maintaining the lower envelope of linear functions.
Study Convex Hull Trick (CHT) DP Optimization Explanation · View Multi-Language Code · All Algorithms