This is not a DP problem. There are no overlapping sub problems or optimal substructure


Comment body goes here.


I solved it without DP after some efforts, but the editorial does provide a working DP solution. It wasn’t intuitive to me either, but it exists.


Sure, you could argue that any problem is a DP then. For example finding min among a list of numbers: min(A1…An) = min(min(A…An-1)), An). Using the term DP for such trivial sub problems which collapse into a single state is misleading


@avin-m Calm down bro. This is surely a valid DP problem.