Leetcode 926. Flip String to Monotone Increasing

Oct. 20, 2018

Introduction

It is a medium level algorithm. I thought about the solution in weekly contest 107 over 10 minutes, but I could not come out the solution in the limited time. So this is my perfect time to learn the algorithm.

Good idea 

Here is one of sharing written in Chinese.

这道题是一维数组加状态机的动态规划。
我们假定DP J，是到J位符合递增的序列. 那么根据J位是0或1，我们会有2个状态。
如果J位是0，我们只能从J-1位是0得过来。同时如果这个是字符串的第J个和最后的状态要求不同，需要翻成对应字符而需要+1。
如果J位是1，我们可以从J-1位是0 或者J-1位是1得过来。同时如果这个是字符串的第J个和最后的状态要求不同，需要翻成对应字符而需要+1。

作者：西部小笼包
链接：https://www.jianshu.com/p/c8dbaaf87644
來源：简书
简书著作权归作者所有，任何形式的转载都请联系作者获得授权并注明出处。