Exactly correct!!!
But for the proof and solution to be complete, we need to analyze this
for 7 the answer you have is dp[3]=3*dp[2]+1=3*[4]+1
Now can you see that for dp[2], the number of steps would be
000
010
011
That would be only 3 steps so dp[2] is only 3 . Am i correct?
Regards
karthik
