[算法]有人问了这么个算法题

rickxbx

给一个string, 该string所有character都是int， 比如"303"
再给一个target integer, 比如 6

要求在给的string中插入加法运算符号(可多个)， 使其值与target相等。

在给出的例子里， 3+03 = 6



并求出插入加法符号最少的个数。

比如同样这个例子， 也可以是3+0+3 = 6， 但插入了两个符号， 不是最小值。

arxor

target 多大? 不是非常大的话dp就好了吧

设target为m, 串长n

f(i, k)表示前i个digit构成k需要的最小"+"号数
有

f(0, 0) = 0
f(0, k) = inf, (k > 0)
f(i, k) = min(f(j - 1, k - value(j, i)) + 1), (j >= 1, k >=0)

这里value(j, i) 表示串[j, i]构成的数字
所求就是f(n, m)

时间复杂度O(m*n^2)

Please correct me if I'm wrong.

Iambitious

It's right

rickxbx

正解,,,,