Asked in my Meesho OA last week.

Define dp[i] as the answer for the first i elements and write the transition from smaller states. Once it works, notice you only need the previous row/value, so space drops to O(1) or O(n).