Neurons are used for more tasks than just problem-solving. Dogs have a good smell, so a big part of their brain is probably used for just this. They seem to be also much more acrobatic and reacting faster in general than an Octopus, so theses are probably also areas where additional neurons are used. Dogs have also a high social intelligence, not sure how Octopi are in that regard.
And are Octopi really better at problem-solving than a dog in general?
> reacting faster in general than an Octopus
It may be due to myelin[1], or rather lack of it. Neurons pass signals along axons as a wave of an action potential[2]. It is a process involving moving ions through the cell membrane to change local deviations of electrical charge and it goes like a wave. The wave is pretty slow. It can be sped up by making axons thicker, and IIRC octopuses has some wildly thick axons you can see without a microscope.
Vertebrates learned how to create an myelin isolation on axons with small gaps, so ion exchanges happen only at these gaps, and between them there is other mechanism to transfer charges, I think it is just "normal" electric current in electrolyte. It is much faster. I'd bet that the slowness of octopuses is not due to neuron count, but due to outmoded axons.
[1] https://en.wikipedia.org/wiki/Myelin
[2] https://en.wikipedia.org/wiki/Action_potential