I changed the permalink structure from
How can I redirect all old posts to the new ones (eg: via htaccess)?
WordPress should handle the 301 redirects for you automatically in this case. It doesn't always, but it should here.
Long story short, WordPress has a function,
You can also redirect via WP. Yes, the htaccess variant is with better performance, but a small plugin is easy to use.
Use the Hook