• tzl2093
• 2017-07-08

你说的原题，我做了一下，用了简单的字典就能做出来。可是我还是看不懂别人第二题的代码，不明白大多数人代码中的两个状态分别代表什么意思，好忧伤。

• bfsoyc
• 2017-09-11

我觉得这两题还是不太一样的，希望下面的理解有所帮助 我们用s(i)表示原串中长度为i的前缀所表示的数，如样例"1111"， s(1) = 1， s(3) = 7 f[i] 表示获得s(i)的最小操作次数。 a.如果第i+1位是0,那么f[i+1] = f[i] b.如果第i+1位是1,有两种方案： 要么先以f[i]次操作构造出 (s(i)<<1) ,然后加1（需要额外一次操作） 要么先构造出 s(i+1) + 1 ， 然后减1， 现在问题是我们不知道构造s(i+1)+1这个数的最少操作次数， 可以发现，s(i+1)+1末位一定是0，在上述情况a中我们已经知道，此时构造s(i+1)+1的操作次数与构造s(i)+1的操作次数是一样的 如构造 s(3)+1 = "1000" = 8 的步数与构造 s(2)+1 = "100" = 4的次数是一样的。 于是记 g[i] 为获得s(i)+1的最小操作次数。 于是有 f[i+1] = min( f[i]+1, g[i]+1 ) 至于g[i]的递推方程，请自行斟酌。 另一种理解方式为g[i]表示向右"借位"的状态。