It was a programming challenge, in which we had to find the shortest set of database strings (of which there were a few millions), that concatenated together would give target string (that we had to find on the internet as osint part of the challenge). The strings weren't very long; around 100 characters each, and the target string was two orders of magnitude longer. Simple brute force wouldn't work.
Instead, we opted for dynamic programming solution: for each substring of the target, we calculated the minimal
solution by brute forcing first division point and fetching subproblem solution from memoized array. This gave
us runtime of O(N*N*M), where N is length of the target, and M - maximum length of database strings (with
possibly some logarithmic overhead from Python data structures). Full code attached.