代码之家 › 专栏 › 技术社区 › Rich

从剪贴杂志人物中生成一条信息(采访问题)

dynamic-programming algorithm

Rich · 技术社区 · 16 年前

这个问题出自本书的动态规划一章 算法设计手册 斯基纳。

我用回溯法解决了这个问题,但是因为它在动态规划一章中,我想一定有一个我不能理解的循环。谁能给我一个提示吗?

2 回复 | 直到 16 年前

Aryabhatta Aryabhatta 16 年前

你可以用最大二部匹配来解决它。

库的每对字符(R1、R2)构成正确的集。

在结果图中找到最大匹配。如果所有左顶点都是匹配的一部分,那么您就得到了答案。否则,这样的字符串是不可能的。

看到了吗 Maximum Bipartite Matchings 一个算法。

不知道这是否是最佳的,虽然和抱歉没有回答完全按照要求。

Tom Sirgedas 16 年前

如果你有一个递归回溯解决方案,你也许可以申请 memoization

推荐文章

William Edwardson · 最长重复子序列:边缘情况

2 年前

Manisha Mns · 如何在C语言中使用并行性将数据表转换为动态对象#

2 年前

Srinivasan A · 动态编程:(不吃冰淇淋的最短天数)

2 年前

Tzvi Gregory Kaidanov · 什么样的样板文件最适合使用reactjs typescript和进行动态表单构建。网芯微服务

2 年前

valerii15298 · 所有可能的不同的不递减的数字序列(组合),以快速达到给定的总和

2 年前

user22847357 · 如何输出字典中最小的一个最短的超弦?

2 年前

DARK FOREST · 为什么——i和i-1在递归中产生不同的输出?

3 年前

Shefali Goel · 替换圆形阵列的相邻元素以使所有元素相等-DSA采访问题

3 年前

THN · 为什么timeit会导致所有内存运行的时间几乎不变?

3 年前

Silva He · 如何使用动态编程来解决区间覆盖问题?

3 年前