Dynamic Programming

Convex Hull DP Optimization

$dp[i][j]={\min }_{k<j}(dp[i-1][k]+b[k]\ast a[j])$