C中的动态编程资源？

Question

我明天将把在线Google测试写成更新鲜的.显然,他们肯定会在动态编程上遇到一个问题？

有谁知道在C中收集DP问题的好资源以及解决方案？我知道什么是DP并且在一次或两次使用过它.但是我觉得在测试中破解DP问题,以前的典型问题的实践将使其更容易接近.

任何有关C解决方案的良好资源或问题集都将受到高度赞赏.谢谢.

Answer 1

好的,所以我真的希望这不算"无耻的自我推销",因为所有这些链接都是我在个人网站上发布的代码片段.如果这不合适,请告诉我,我可以将它们删除.

这里有一些有趣的DP问题,几乎是经典的:

1. 最小编辑距离:给定两个字符串A和B,找到将A转换为B所需的最短编辑数(插入,删除或替换).这称为Levenshtein距离. (我的解决方案)
2. 最佳序列比对:给定两个字符串A和B,找到必须插入序列以对齐A和B的最小间隙数.这称为Needleman-Wunsch算法.(我的解决方案)
3. 单源最短路径:给定一个有向图G和一个单一的节点s,找到从s到图中的每个其它节点的最短路径的长度,假定边缘可以是正或负,但是没有循环存在.这是Bellman-Ford算法.(我的解决方案)
4. 全对最短路径:给定有向图G,找到所有节点对之间的最小距离.这是Floyd-Warshall算法.(我的解决方案)

希望这有点有用,祝你明天好运!