Not a DP problem


This problem is solvable by DP, but DP is not the most optimal approach for solving this. A better solution is available using a specific Data structure. I feel this may mislead people as dp makes the code complex and they may still go after it.