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


#1

Comment body goes here.


#2

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.


#3

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


#4

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