How to optimize this DP solution?

Revision en3, by suzie_q, 2022-04-23 02:40:30

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)$$$?

UPD: I forgot to mention that the array $$$b$$$ is monotone (ie $$$b[i] \leq b[i+1]$$$). Don't know if that helps though...

Tags dp, optimization

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English 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 English suzie_q 2022-04-23 02:40:30 123 Tiny change: '{O}(n^2)$?' -> '{O}(n^2)$?\n\n**UPD:**'
en2 English suzie_q 2022-04-22 23:14:22 1
en1 English suzie_q 2022-04-22 23:13:37 366 Initial revision (published)