明天我将作为新人编写在线 Google 测试。显然，他们肯定会问一个关于动态编程的问题？
有谁知道在 C 中收集 DP 问题以及解决方案的好资源？我知道 DP 是什么，并且曾经使用过一两次。但是我觉得在测试中破解一个DP问题，典型问题的先前实践将使其更容易接近。
任何具有 C 语言解决方案的好的资源或问题集都将受到高度赞赏。谢谢。
问问题
1697 次
4 回答
8
好的，所以我真的希望这不会算作“无耻的自我推销”，因为所有这些链接都是我在个人网站上发布的代码片段。如果这不合适，请告诉我，我可以删除它们。
以下是一些非常经典的有趣 DP 问题：
- 最小编辑距离：给定两个字符串 A 和 B，找到将 A 转换为 B 所需的最短编辑次数（插入、删除或替换）。这称为 Levenshtein 距离。 （我的解决方案）
- 最佳序列比对：给定两个字符串 A 和 B，找出必须插入序列中以比对 A 和 B 的最小间隙数。这称为 Needleman-Wunsch 算法。（我的解决方案）
- 单源最短路径：给定一个有向图 G 和单个节点 s，假设边可以是正的或负的，但不存在环，则找出从 s 到图中每个其他节点的最短路径的长度。这是贝尔曼-福特算法。（我的解决方案）
- 所有对最短路径：给定一个有向图 G，找到所有节点对之间的最小距离。这就是 Floyd-Warshall 算法。（我的解决方案）
希望这有点用处，祝你明天好运！
于 2011-01-09T08:38:27.540 回答
1
Topcoder网站很棒。并非所有问题都使用 DP，但很多问题都使用。免费完全访问过去比赛中的所有问题，这些问题有 3 个不同的难度级别，以及问题作者对每个问题的赛后解释。不仅如此，你还可以快速挖掘出比赛中任何编码员提交的源代码解决方案。
已经有一段时间没有回到那里了，但它们至少允许使用 C++、Java、C#，我现在相信还有其他几种语言。
于 2011-01-09T09:28:10.767 回答
1
我建议你，收集一本书“生物信息学算法简介”。这有一章完全关于 DP。正如@templatetypedef 提到的最小编辑距离，最佳序列对齐它有其他问题。虽然它没有实现。你必须自己做。但你会发现阅读它们很有趣。
于 2011-01-09T10:37:42.057 回答
1
练习时，您可以在 SPOJ 解决可用的问题之一。要轻松识别 DP，您可以查看问题分类器（关键字：dp）。
于 2011-01-09T12:22:14.497 回答