Target Time Complexity?

Problems and Contests
#1

I’m looking at this problem from the Range DP module.

Is the target complexity \mathcal{O}(n^3)? I initially thought it would be \mathcal{O}(n^2), but then this part wouldn’t make sense:
image

#2

lol, being silver, I should probably not be helping you but if you want to check the editorial it says \mathcal{O}(n^3) (typos…)

#3

Thanks!

1 Like
#4

Your Welcome