DP最小加法表达式

题:有一个由1..9组成的数字串.问如果将m个加号插入到这个数字串中,在各种可能形成的表达式中,值最小的那个表达式的值是多少

状态转移:

if m = 0

V(m,n) = Num(1,m)

else if n < m + 1

V(m,n) = ∞

else

V(m,n) = Min{ V(m-1,i) + Num(i+1,n) } ( i = m … n-1)


Num(i,j)表示从第i个数字到第j个数字所组成的数。数字编号从1开始算。

V(m,n) 表示在n个数字中插m个加号组成的最小数

此操作复杂度是O(j-i+1)

总时间复杂度: O(mn2)

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 12,775评论 0 33
  • 1. Java基础部分 基础部分的顺序:基本语法,类相关的语法,内部类的语法,继承相关的语法,异常的语法,线程的语...
    子非鱼_t_阅读 31,767评论 18 399
  • 职场精英:安迪 安迪高智商、高学问、高收入,外人所艳羡的都拥有的大美女,凡人所不能及,独立高傲是她的外标签。敏感不...
    追余莫待阅读 490评论 2 3
  • (一) 荷花 你告诉我 洁净和污泥 你选哪个? (二) 在风起前的那一刻 树叶何曾知道 追随的方向 (三) 所有事...
    墨绮阅读 208评论 5 13
  • 一、表与表之间的关系回顾 一对多建表时,通过外键来建表: 多对多建表时,要维护第三张表: 二、hibernate配...
    exmexm阅读 687评论 0 1