I'm honestly somewhat surprised that you-know-who is asking DP problems with that degree of complexity. Are you applying for a research/math-heavy role? If you're unlucky enough to see DP, usually it's pretty basic and memoization is considered fine, unless things have changed very recently. If they required that degree of rigor for regular SWE jobs, a lot of people I know certainly wouldn't be there.