I've lately been struggling to write correctness proofs for various algorithms, even when it is "obvious" to me that the algorithm works and is correct. For example, take the following problem:
Given a binary string $s$ of length $n$, you can perform an invert operation on index $i$ (0-indexed) which inverts the prefix of $s$ from index $0$ to index $i$ inclusive for a cost of $i+1$. What is the minimum total cost needed to make all characters of the string identical (i.e. $s$ will either be the string of all $0$s or the string of all $1$s)?
It is clear (to me) that the optimal way to do this is to simply loop through the array and invert the first $i$ characters to match the next character. But I am not sure how to turn this into a proof of optimality. An arbitrary algorithm could do something crazy, and I'm not sure how to argue that anything crazy is not better than the above algorithm. I'm looking for something rigorous, and not just the proof, but for the thought process leading up to the proof, because I want to be able to solve similar problems and convince myself that my solution is indeed definitely optimal.