dyld: Library not loaded: /usr/local/opt/icu4c/lib/libicuio.66.dylib

Just brew remove php and brew install php did not work, nor did brew reinstall php.
My solution was to do:
brew remove php
cd /usr/local/Cellar
rm -rf php/
brew install php
brew doctor
brew cleanup
Now php -v gives me:
PHP 7.3.2 (cli) (built: Feb 14 2019 10:08:45) ( NTS )