Recently came across this interesting question based on recursion, however almost every where tabulation based solution is present. So check out the recursive version on the same. PS: If you are looking for optimal solution just go ahead and memoize it. Will take at max 4–5 lines changes to the above proposed solution. Also if you want to see the recursion tree uncomment the cout statement in solver