I also did BAT2 and BORW using both top-down and bottom-up DP. For the BORW problem (in which the time taken is more conspicuous), the top-down solution gives 1.74s while the bottom-up solution gives 2.94s. The contrast between this and my earlier solution of 0.45s can be explained due to the former's time complexity being O(n^3) while the latter's is only O(n^2 log n).

The difference between both DP solutions is surprising and counter-intuitive. Perhaps it is because a lot of 3d dp states are not achieved but are nevertheless filled in the bottom-up approach, while the recursion is very economical in this regard. Is this right? Are there any other factors affecting the runtimes?

Here are my DP solutions for BORW:

#include <bits/stdc++.h>

using namespace std;

int n;

int a[201];

int c[201][201][201];

int f(int ti, int td, int i)

{

if(i == n + 1)

return 0;

if(c[ti][td][i] != -1)

return c[ti][td][i];

int mx = 0;

if(!ti || a[i] > a[ti])

mx = 1 + f(i, td, i+1);

if(!td || a[i] < a[td])

mx = max(mx, 1 + f(ti, i, i+1));

mx = max(mx, f(ti, td, i+1));

c[ti][td][i] = mx;

return mx;

}

int main()

{

while(true)

{

cin >> n;

if(n == -1)

break;

for(int i = 1; i <= n; ++i)

cin >> a[i];

memset(c, -1, sizeof c);

cout << n - f(0, 0, 1) << '\n';

}

}

#include <bits/stdc++.h>

using namespace std;

int n;

int a[201];

int c[201][201][202];

int main()

{

while(true)

{

cin >> n;

if(n == -1) break;

for(int i = 1; i <= n; ++i)

cin >> a[i];

memset(c, 0, sizeof c);

for(int i = n; i > 0; --i)

{

for(int ti = 0; ti <= n; ++ti)

{

for(int td = 0; td <= n; ++td)

{

int mx = 0;

if(!ti || a[i] > a[ti])

mx = 1 + c[i][td][i+1];

if(!td || a[i] < a[td])

mx = max(mx, 1 + c[ti][i][i+1]);

mx = max(mx, c[ti][td][i+1]);

c[ti][td][i] = mx;

}

}

}

cout << n - c[0][0][1] << '\n';

}

}