Browse Category

线性DP

Leetcode LCP 19 秋叶收藏集 (dp)

给定一个字符串,例如 rrryyyrryyyrr,每次操作可以将 r 变为 y,或者相反。目标是要让该字符串变为形如 rrryyrrr 的样式,即「红、黄、红」,每一段的数量可以不等但不可以为空,问最小的操作次数。

Leetcode 1039 Minimum Score Triangulation of Polygon (dp)

假设您将多边形剖分为 N-2 个三角形,对于每个三角形,该三角形的值是顶点标记的乘积,三角剖分的分数是进行三角剖分后所有 N-2 个三角形的值之和。
返回多边形进行三角剖分后可以得到的最低分。

LOJ 6160 二分图染色 (dp,组合数学)

给定一个完全二分图,图的左右两边的顶点数目相同。我们要把图中的每条边染成红色、蓝色、或者绿色,并使得任意两条红边不共享端点、同时任意两条蓝边也不共享端点。计算所有满足条件的染色的方案数,并对 10^9+7 取模。