How best to prevent memory exhaustion in time-critical dynamic programming?

[superbonzo]

the performance begins to drop on some inputs and the program crashes due to memory exhaustion (or maybe fragmentation???) on others.

can't you catch the memory allocation error and the performance decrease at runtime and then shrink the memory consumed by the algorithm accordingly ? I ask, because you alluded to a time critical code yet running on the seconds order-of-magnitude time scale, hence such an auto profiling/error handling code should not impact the running time significantly anyway ...