Dp optimisation

Consider a dp, where dp_{i,j} is true if dp_{a,x}\ \&\ dp_{b,y} is true for some a,b,x,y where a + b = i-1 and x + y = j - i + 1. Let’s say we want all values till dp_{n,m}. Is it possible to compute it in O(nm) time?.
Question it’s taken from : https://codeforces.com/problemset/problem/1311/E
@galencolin
I know the constructive solution.

1 Like