|
发表于 2007-1-11 21:14:45
|
显示全部楼层
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. |
|