问题标签 [dynamic-programming]

几乎按照定义，动态编程是在隐式 dag 上找到最短/最长路径。每个 DP 算法都是这样做的。

全息算法可以粗略地描述为在隐式平面图中计算完美匹配的东西。

所以，我的问题是：是否还有其他算法家族在隐式图上使用众所周知的算法来实现相当大的加速？

我对如何最好地设计这个算法感到困惑。一艘船有 x 个海盗，其中第 j^个海盗的年龄为 a _{j ，第 j}^个海盗的体重为 w _j。我正在考虑一种动态规划算法，它将找到体重在所有海盗的百分之二十五到七十五之间的最年长的海盗。但我不知道如何进行。

我有两个非常大的字符串，我正在尝试找出它们的Longest Common Substring。

一种方法是使用后缀树（假设具有非常好的复杂性，尽管实现复杂），另一种是动态编程方法（以上链接的维基百科页面都提到了这两种方法）。

使用动态规划

问题是动态规划方法的运行时间很长（复杂度是O(n*m), wheren和m是两个字符串的长度）。

我想知道的（在开始实现后缀树之前）：如果我只想知道公共子字符串的长度（而不是公共子字符串本身），是否可以加快算法速度？

我有这个程序

是否可以使用动态编程加快速度？

我发现这个函数在 O(2^n) 中运行

我应该通过动态编程来减少运行时间，但不理解这个概念。

只是要求朝正确的方向轻推。

我正在尝试使用动态编程解决点游戏的变体。

常规的点游戏是用一排点来玩的。每个玩家在他们各自的线端取一个或两个点，没有点的人获胜。

在这个版本的游戏中，每个点都有不同的值。每个玩家轮流轮流，并在线路的两端取任意一个点。我想想出一种方法来使用动态编程来找到第一个玩家可以保证获胜的最大金额。

我在解决这个问题并试图为解决方案编写重复出现时遇到问题。任何帮助表示赞赏，谢谢！

给定一个序列，比如 222 我们必须在每个相邻对之间放置一个“+”或“*”。'*' 优先于 '+'

我们必须 o/p 其评估导致最小值的字符串。如果有多个，O/p 必须是字典最小的。

输入：222

o/p：2*2+2

解释：

2+2+2=6

2+2*2=6

2*2+2=6

这个 3rd 在字典上是最小的。

我想知道如何为此构建一个 DP 解决方案。

我应该为立体匹配问题实现动态编程算法。我已经阅读了 2 篇研究论文，但仍然不明白如何为此编写自己的 c++ 程序！

是否有任何书籍或资源可供我用来了解如何实际开始编码？

互联网搜索只给我关于动态编程的期刊和会议论文，而不是如何逐步实现算法。

谢谢

瓦伦

我想对以下 MATLAB 代码进行矢量化。我认为它一定很简单，但我发现它仍然令人困惑。

代码从另一个得分表C计算动态编程算法的得分表S。 对角线求和是为用于生成C的各个数据片段生成分数，用于所有可能的片段（大小为 r）。

提前感谢您的任何答案！对不起，如果这个应该很明显......

注意
内置的 conv2 比 convnfft 更快，因为我的 eye(r) 非常小（ 5 <= r <= 20 ）。convnfft.m 声明 r 应该 > 20 才能体现任何好处。

我试图了解什么是链矩阵乘法以及它与常规乘法有何不同。我已经检查了几个来源，但似乎都非常学术性地解释给我理解。

我想这是一种动态规划算法，以优化的方式实现操作，但我没有更进一步。

谢谢

我有大约 5,000 个矩阵，它们具有相同的行数和不同的列数（20 x ~200）。这些矩阵中的每一个都必须在动态规划算法中相互比较。

在这个问题中，我询问了如何快速进行比较，并得到了一个涉及 2D 卷积的出色答案。连续地，迭代地应用该方法，就像这样

对于数据的小子集来说速度很快（例如，对于 9 个矩阵，9*9 - 9 = 72 次调用在 ~1 秒内进行，870 次调用在 ~2.5 秒内）。
然而，对所有数据进行操作需要近 2500 万次调用。
我还尝试使用 deal() 来制作一个完全由数据中的下一个元素组成的单元格数组，因此我可以在单个循环中使用 cellfun() ：

不幸的是，这并没有真正更快，因为所有时间都在 compare() 中。这两个代码示例似乎都不适合并行化。我无法弄清楚如何对变量进行切片。
compare() 是完全向量化的；它专门使用矩阵乘法和 conv2()（我的印象是所有这些操作，包括 cellfun()，都应该在 MATLAB 中是多线程的？）。

有没有人看到（明确的）并行化解决方案或更好的问题向量化？

注意
我意识到我的两个例子都是低效的——如果它计算一个三角形单元阵列，第一个例子的速度会快两倍，而第二个例子仍然在计算自我比较。但是，良好的并行化所节省的时间更像是 16 倍（如果我在每个人的机器上安装 MATLAB，则为 72 倍）。

另外
还有内存问题。我使用了几个 eval 将 H 的每一列附加到一个文件中，名称如 H1、H2 等，然后清除 H _i。不幸的是，保存速度很慢......