How to optimize this DP solution

Правка en1, от suzie_q, 2022-04-22 23:13:37

We are given two arrays $$$a$$$ and $$$b$$$ of length $$$n$$$. Consider the following recurrence relation:

$$$f(i) = \displaystyle \min_{b[i]\; \leq\; j\; <\; i}\big\{f(j)+ \max(a[j+1], \dots, a[i])\big\}$$$

We are interested in calculating $$$f(n)$$$. Is there a way to calculate it with the time complexity being better than $$$\mathcal{O}(n^2)$$$?

Теги dp, optimization

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en4 Английский suzie_q 2022-04-23 02:41:14 16 Tiny change: 'ay $b$ is monotone (ie $b[i] \le' -> 'ay $b$ is increasing (i.e. $b[i] \le'
en3 Английский suzie_q 2022-04-23 02:40:30 123 Tiny change: '{O}(n^2)$?' -> '{O}(n^2)$?\n\n**UPD:**'
en2 Английский suzie_q 2022-04-22 23:14:22 1
en1 Английский suzie_q 2022-04-22 23:13:37 366 Initial revision (published)