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

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

dynamic-programming algorithm

Rich · 技术社区 · 15 年前

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

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

2 回复 | 直到 15 年前

Aryabhatta Aryabhatta 15 年前

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

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

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

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

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

Tom Sirgedas 15 年前

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

推荐文章

Matthew Thomas · 在每个决策中给出多个选择的所有可能的决策路径/结果

1 年前

feasega · 聚合物模拟-2个节点之间的最短路线,适用于所有节点

1 年前

Alisa Petrova · 在有向图中更改一对顶点以创建循环

1 年前

Matvey Androsyuk · 如何使用React在树结构中呈现我的组件,就像IDE中的默认文件结构一样

1 年前

Pengcheng · 这个简单的递归函数的输出是什么?你能详细解释一下吗?

1 年前

b39b332d · 使用C++标准库实现高效间隔存储

1 年前

Paul C · 在维基百科上,将二叉搜索树转换为排序链表的算法是否存在错误?

1 年前

ABGR · 二叉树的直径——当最长路径不通过根时的失败案例

1 年前

SHUBHAM KUMAR · 这两个是否完全相同-->“下限(股份有限公司rbegin(),股份有限公司rend(),i,更大<int>())”和“下限(dec.begin(

1 年前

EpicAshman · 数独棋盘程序中同一列和同一行出现两次的数字

1 年前