Yeah, sorry, i should have done so in my first post.

Let's talk about a general DP(N, S), like you suggested. Let's define f(left, right, K) with 1 ≤ left ≤ right ≤ N and 0 ≤ k ≤ S our subroutine, which besides computing the optimal answer, also prints the solution. Imagine the solution is a path in the DP table. We want to cut the path so that we end up with 2 smaller subproblems of (almost) equal size. The way to go is definitely chosing the middle line, but where exactly? If we don't chose the right point to recurse, we will print a solution which has nothing to do with the final answer. Therefore, we need to find for DP(right, K) the point 0 ≤ P ≤ K where the optimal solution for DP(right, K) intersects the middle line. This should be do-able in O(N) additional memory. This may vary from task to task, but i will offer an example for the knapsack task, e.g. suppose going from DP(i - 1, j) to DP(i, j + weight[i]) improves the solution, then:

if (i <= middle)
   reconstruct[line][j + weight[i]] = j + weight[i]
else
   reconstruct[line][j + weight[i]] = reconstruct[previous_line][j]

(where line and previous_line are 0/1 accordingly, the usual memory optimization)

Our calls to the smaller subroutines are obvious now:

f(left, right, K):
  ...
  optimal_middle_cut_point = reconstruct[last_line][K]
  
  f(left, middle, optimal_middle_cut_point)
  f(middle + 1, right, K - optimal_middle_cut_point)

(Credits for this diagram goes to bioinformaticsonline.org)

Let's analyse the time complexity now (for the knapsack problem for example):

T(N, K) = O(NK) + T(N / 2, P) + T(N / 2, K - P)

Look at the areas of the first smaller subroutines. They add up to . The next ones will add up to and so on, therefore the final complexity is O(NK * (1 + 1 / 2 + 1 / 4 + ..)) = O(2 * NK). A small cost for such a memory reduction.

The only task i've ever solved using this trick is called ghiozdan, that's Romanian for knapsack. It's a good task, combining both the Bounded knapsack and the Hirschberg tricks. I'll make a quick tl;dr: you want to fill up a knapsack of size less or equal than 75000 using as few items as possible from a list of at most 20000. Time limit is 2 seconds and the memory limit is 16384 kbytes. Sadly, iirc it has weak tests, but if you want to learn something new you should try solving it in a legitimate manner.

Feel free to ask if anything is left unclear, wrong or just explained poorly. I'll do my best to fix it.