Android Studio not deploying changes to app
I've got the same problem. This thread popped up first when I've searched for it. Solved it (hoping so) by not using the Instant Run feature. Might not be the best solution but it works for now.
Just go to "File -> Settings -> Build, Execution, Deployement -> Instant Run" and just disable it. With this Android Studio builds from scratch each time but it's better than not building it right.
Mini rant: Almost each version of Android Studio comes with an annoying bug. They're about to release the version 2 but its beta is still buggy. I hope they stabilize the IDE in the near future.
EDIT2 (2020-03-09)
If you are using gradle 6.0 in your gradle-wrapper.properties, you may also encounter a similar situation because there is this bug in 6.0 version. Try 6.0.1 instead.
Yesterday (2018-03-27) Android Studio published an official update from 3.0.1 to 3.1, and it looks like a lot of people (including me) start running into this issue again.
Credit to #5 comment here, below is how it solved:
In Android Studio, go to Run > Edit Configuration.
Under Before launch:, if you cannot find Gradle-aware Make, just like below:
Add Gradle-aware Make and leaving Task empty.
Warning: I don't know what these action means, and whether it will cause any side-effects. Appreciate if someone can give more explanation on it!
EDIT
Thanks to @ChristopherSmit referenced, this page mentions that Gradle-aware make means "Compile the project and run Gradle".
At first I guess this may make Runs take longer time even if no code has been changed; but after testing, the second time is still much faster if no code has been changed.
Given that fact that this is a default option if you create a new project using AS 3.1, I think this configuration is pretty safe.