经典动态规划模型归纳总结(最大连续子序列和、LIS、LCS、最长回文子串、数塔DP、DAG最长路、01背包、完全背包)

https://blog.csdn.net/qq_33375598/article/details/104464435

1 模型列举

1.1最大连续子序列和

详细内容
令dp[i]表示A[i]结尾的连续序列最大和(A[i]必须为连续序列的末尾)【不然就会产生多个相同的dp[i]】。

状态转移方程:
边界:

1.2最长不下降子序列(LIS)

详细内容
令dp[i]表示最长不下降序列长度(必须以A[i]结尾)。

状态转移方程

边界:

1.3 最长公共子序列LCS

详细内容
令dp[i][j]表示字符串A的i号位和字符串B的j号位之前的LCS长度(下标从1开始)。

状态转移方程
$dp[i][0] = dp[0][j] = 0(0<= i <= n, 0 <= j <=m)$

1.4 最长回文子串

详细内容
令dp[i][j]表示S[i]至S[j]所表示的子串是否是回文串,是则为1,不是为0。

状态转移方程
$$

边界:

1.5 数塔DP

详细内容
令dp[i][j]表示从第i行第j个数字出发的到达最低层的所有路径上所能得到的最大和。

状态转移方程
边界(直接确定其结果):数组dp最后一层dp总是等于元素自身

1.6 DAG最长路

详细内容
令dp[i]表示从i号顶点出发的获得的最长路径长度。

状态转移方程
不固定终点/不固定终点:
边界:
不固定终点:
从出度为0的顶点出发的最长路径长度为0(对整个数组dp初始化为0)
固定终点: (T为终点,初始化dp数组作为一个负的大数)

1.8 0-1背包

详细内容
令dp[i][v]表示前i件物品( 1 i n, 0 v V)恰好装入容量为v的背包中所能获得的最大值。

状态转移方程

边界:

1.9 完全背包

详细内容
令dp[i][v]表示前i件物品( 1 i n, 0 v V)恰好装入容量为v的背包中所能获得的最大值。

状态转移方程:
边界:

2 总结

2.1 类型一

XXX:为原问题的描述

  • 第一节1~4都是有关序列或字符串的问题(一般来说“子序列可以不连续、子串必须要连续”),
    • (1)(2)的设计状态都是“令dp[i]表示以A[i]结尾的XXX”,
    • 而 (3)(4)由于原问题本身就有二维性质,因此使用了“令dp[i][j]表示i号位和j号位之间XXX“的状态设计方式“

当题目与序列和字符串(记为A)有关时,可以考虑把状态设计为下面两种形式,然后根据端点特性考虑状态转移方程。

  • 1 令dp[i]表示以A[i]结尾(或开头)的XXX;
  • 2 令dp[i][j]表示i号位和j号位之间XXX。

    2.2 类型二

    (5)~(8),它们的状态设计都包括了某种“方向” 的意思,
    如数塔DP设计为从(i,j)出发到达最底层的最大和
    DAG设计为从i号顶点出发的最长路
    背包问题设计为前i件物品恰好放容量为v的背包中能获得的最大价值。

当题目中的状态需要几维来表示,然后对其中的每一维采取下面的某一种描述:

  • 1 恰好为i;
  • 2 前i;
    在每一维的含义设计完毕之后,dp数组的含义就可以设置为“令dp数组恰好为i(或前i),恰好为j(或前j)……的XXX”,然后就可以通过端点的特性来考虑状态转移方程。

大多数情况,可以把动态规划可解的问题看成一个有向无环图(DAG),图中的结点就是状态,边就是状态转移方向,求解问题的顺序就可以按照DAG的拓扑顺序进行求解。

全部评论

相关推荐

感觉这一周太梦幻了,就像一个梦,很不真实~~~感觉这个暑期,我的运气占了99成,实力只有百分之一4.15上午&nbsp;腾讯csig&nbsp;腾讯云部门,面完秒进入复试状态4.16下午&nbsp;美团优选供应链部门,4.18上午发二面4.17晚上&nbsp;阿里国际一面,纯拷打,面完我都玉玉了4.18下午&nbsp;阿里国际二面,是我们leader面的我,很轻松~~4.18晚上&nbsp;约了hr面4.19上午&nbsp;hr面,下午两点口头oc4.19晚上&nbsp;意向书说起来我的暑期好像一次都没挂过~~~~~难道我是天生面试圣体?----------------------------------------------------------------------六个月前,我还是0项目0刷题,当时想的是先把论文发出来再去找实习。结果一次组会,老师打破了我的幻想(不让投B会,只让投刊或者A)我拿头投啊!!!然后就开始物色着找实习,顺便做完了mit的6.s081,但是基本上还是没刷过题目-----------------------------------------------------------------------11月&nbsp;&nbsp;一次偶然的机会,面进了某个耳机厂的手环部门,大概是做嵌入式的,用的是CPP。12月&nbsp;莫名其妙拿到了国创的面试机会,0基础四天速成java基础!居然也给我面过了hhhhh,可能是面试没写题吧入职国创后的几个月,一直没活,天天搁那看剧,都快忘了还有暑期实习这回事了~~~~命运的齿轮在2.26开始转动,因为这一天美团开了,我开始慌了,因为那时的我什么都不会。lc,八股,sql全部是0进度。然后就开始了女娲补天,上班刷题,下班继续做之前的开源,顺便学一学八股。3月到现在,lc也刷到快200了,一天最多提交了47次~~~~~~~~~~八股根据别人的面经总结和博客,写了快十万字的笔记~~~~~~~~~~简历上的实习经历和开源,也努力去深挖了,写了几万字的记录~~~~~~所以面试的时候,基本上都能cover了,面试官问到的基础基本都会,不基础的我就把他往我会的地方引。结果好像还不错,基本上每个面试官评价都挺好的emmmmmmmm
投递阿里巴巴等公司10个岗位
点赞 评论 收藏
转发
点赞 收藏 评论
分享
牛客网
牛客企业服务