dp problems r combinatorics.i dont know why people dont use some kind of permutation and combination formula.idk how adding some random states like dp[i]=dp[i-1] bla bla bla works.pretty dumb concept if u ask me.