问题标签 [dynamic-programming]

创建一个像下面这样可以为您处理记忆过程的类是“好习惯”吗？memoization 的好处是如此之大（在某些情况下，比如这个，它在我的计算机上从 501003 到 1507 个函数调用以及从 1.409 到 0.006 秒的 CPU 时间），看起来像这样的一个类会很有用。

但是，我只阅读了关于eval(). 考虑到这种方法提供的灵活性，这种用法是否可以原谅？

这可以以失去副作用为代价自动保存任何返回值。谢谢。

考虑一下你有一个价值的问题N，你需要计算有多少种方法可以N用[1,2,5,10,20,50,100]美元钞票来总结美元。

考虑经典的 DP 解决方案：

它不影响相加部分的顺序。例如，comb(4)将产生 5 个结果：[1,1,1,1],[2,1,1],[1,2,1],[1,1,2],[2,2]而实际上有 3 个结果（[2,1,1],[1,2,1],[1,1,2]都相同）。

计算这个问题的 DP 习语是什么？（不欢迎非优雅的解决方案，例如生成所有可能的解决方案和删除重复项）

这个问题来自Skiena的The Algorithm Deisgn Manual中的动态规划章节。

给出一个算法来确定您是否可以通过粘贴杂志上的剪裁来生成给定的字符串。您将获得一个函数，该函数将针对任何给定的字符位置识别字符及其在页面反面的位置。

我通过回溯解决了这个问题，但由于它在动态编程一章中，我认为肯定有重复出现，我无法弄清楚。谁能给我一个提示？

将字符串拆分为单词的正确方法是什么？（字符串不包含任何空格或标点符号）

例如：“stringintowords”->“String Into Words”

你能告诉我这里应该使用什么算法吗？

！更新：对于那些认为这个问题只是出于好奇的人。该算法可用于对域名（“sportandfishing .com”->“SportAndFishing .com”）进行大写，并且该算法目前被 aboutus dot org 用于动态执行此转换。

给定一个任意的钉子纸牌配置，计算导致“游戏结束”位置的任何一系列移动的最有效方法是什么。

例如，标准起始位置是：

而“结束游戏”的位置是：

Peg solitare 在这里有更详细的描述：维基百科，我们正在考虑“英语板”变体。

我很确定在一台合理的计算机上，比如一台 P4 3Ghz，可以在几秒钟内解决任何给定的起始板。

目前这是我最好的策略：

我正在寻找用于 C++ 程序的 LCS 算法的（空间）高效实现。输入是两个随机访问整数序列。
我目前正在使用关于 LCS 的维基百科页面中的动态编程方法。但是，这在内存和时间上有 O(mn) 的行为，并且在我身上死掉了，因为更大的输入会出现内存不足的错误。
我已经阅读了 Hirschberg 的算法，它可以显着提高内存使用率，Hunt-Szymanski 以及 Masek 和 Paterson。由于实现这些并非易事，我更愿意使用现有实现在我的数据上尝试它们。有人知道这样的图书馆吗？我想既然文本差异工具很常见，应该有一些开源库吗？

假设给定一个 mXn 位图，由数组 M[1..m,1..n] 表示，其条目全为 0 或 1。全为 1 的块是 M[i .. i0, 形式的子数组， j .. j0]，其中每个比特都等于 1。描述和分析一种有效的算法，以在 M 中找到最大面积的全一块

我正在尝试制作一个动态编程解决方案。但是我的递归算法在 O(n^n) 时间内运行，即使在记忆化之后，我也无法将其降低到 O(n^4) 以下。有人可以帮我找到更有效的解决方案吗？

假设给定一个 mXn 位图，由数组 M[1..m,1..n] 表示，其条目全为 0 或 1。全为 1 的块是 M[i .. i0, 形式的子数组， j .. j0]，其中每个比特都等于 1。描述和分析一种有效的算法，以在 M 中找到最大面积的全一块

我正在尝试制作一个动态编程解决方案。但是我的递归算法在 O(n^n) 时间内运行，即使在记忆化之后，我也无法将其降低到 O(n^4) 以下。有人可以帮我找到更有效的解决方案吗？

我正在尝试为这个问题提出一个合理的算法：

假设你有一堆球。每个球至少有一种颜色，但也可以是多色的。每个球上也有一个数字。还有一堆盒子，每个盒子只有一种颜色。目标是最大化盒子中球上的数字总和，唯一的规则是：

• 为了将球放入盒子中，它必须至少具有盒子的颜色
• 你只能在每个盒子里放一个球。

例如，您可以将蓝色和绿色的球放入蓝色盒子或绿色盒子，但不能放入红色盒子。

我提出了一些在运行时间方面有很大帮助的优化。例如，您可以按点值的降序对球进行排序。然后当你从最高数字到最低数字时，如果球只有一种颜色，并且没有其他包含该颜色的更高点球，你可以把它放在那个盒子里（然后把那个盒子和那个球从其余组合）。

我只是好奇这种类型的问题是否有某种动态算法，或者只是变相的旅行推销员问题。如果我知道最多有 X 种颜色会有帮助吗？任何帮助是极大的赞赏。谢谢！

编辑 - 这是一个简单的例子：

球：

• 1 个红球 - 5 分
• 1 个蓝球 - 3 分
• 1 个绿球/红球 - 2 分
• 1 个绿/蓝球 - 4 分
• 1 个红/蓝球 - 1 分

盒子：

• 1红色
• 1 蓝色
• 1 绿色

最佳解决方案：

• 红盒子里的红球
• 蓝色盒子里的蓝色球

• 绿盒中的绿/蓝球

  总分：12分（5+3+4）

假设我正在玩 10 种不同的游戏。对于每场比赛，我知道获胜的概率、平局的概率和失败的概率（每场比赛的概率不同）。

从这些值中，我可以计算出赢得 X 场比赛的概率、输掉 X 场比赛的概率以及平局 X 场比赛的概率（对于 X = 0 到 10）。

我只是想弄清楚在打完所有 10 场比赛后赢得W场比赛、平局T场比赛和输掉L场比赛的概率……希望比 O(3^n) 做得更好。例如，赢 7 输 2 平 1 的概率是多少？

有任何想法吗？谢谢！

编辑 - 如果只有 2 场比赛，这里有一些示例数据：

游戏一：

• 胜率：23.3%
• 领带：1.1%
• 损失：75.6%

游戏二：

• 胜率：29.5%
• 领带：3.2%
• 损失：67.3%

基于此，我们可以计算出玩了 2 场比赛后的概率：

• 0胜：54.0%
• 1胜：39.1%
• 2胜：6.9%

• 0 条关系：95.8%
• 1 平：4.2%
• 2 条： 0.0%

• 0 损失：8.0%
• 1 损失：41.1%
• 2 次损失：50.9%

根据这些数字，是否有一个通用公式来计算W胜、T平和L负的概率？可能的结果（WLT）将是：

• 2-0-0
• 1-1-0
• 1-0-1
• 0-1-1
• 0-2-0
• 0-0-2