问题标签 [dynamic-programming]

给定一个电话键盘，如下所示：

从1开始可以组成多少个不同的10位数字？约束是从一个数字到下一个数字的移动类似于国际象棋中马的移动。

例如。如果我们在 1，那么下一个数字可以是 6 或 8，如果我们在 6，那么下一个数字可以是 1、7 或 0。

允许重复数字 - 1616161616 是有效数字。

有没有解决这个问题的多项式时间算法？这个问题要求我们只给出 10 位数字的计数，而不必列出这些数字。

编辑：我尝试将其建模为一个图形，每个数字都有 2 或 3 个数字作为其邻居。然后我使用 DFS 导航到 10 个节点的深度，然后每次达到 10 的深度时增加数字计数。这显然不是多项式时间。假设每个数字只有 2 个邻居，这将需要至少 2^10 次迭代。

这里的变量是位数。我已经采取了例如。10 位数字。它也可以是 n 位数。

如何在 Scheme 中使用数组？

特别是，我正在尝试使用 memoization 实现递归斐波那契过程。数组甚至存在于 Scheme 中吗？

如果没有，我该如何实现记忆？

考虑 2 个序列 X[1..m] 和 Y[1..n]。记忆算法将在 O(m*n) 时间内计算 LCS。有没有更好的算法来找出 LCS wrt time？我猜对角线的记忆可以给我们 O(min(m,n)) 时间复杂度。

我需要在乐曲（例如存储在表格中的音符音高[字符串值]）中针对参考找到 1.mismatch（错误演奏的音符）、2.insertion（附加演奏）和 3.deletion（遗漏的音符）音乐片。

这可以通过精确字符串匹配算法或动态编程/近似字符串匹配算法来实现。但是我意识到，由于识别不匹配、插入、删除注释，近似字符串匹配更适合我的问题。或 Boyer-moore 的扩展版本以支持大约。字符串匹配。

是否有示例 java 代码的链接我可以尝试近似字符串匹配？我找到了复杂的解释和方程式——但我希望我能用一些示例代码和简单的解释做得很好。或者我可以在 boyer-moore 上找到任何示例 java 代码扩展约。字符串匹配？我理解 boyer-moore 的概念，但是在调整它以支持大约。字符串匹配（即支持不匹配、插入、删除）。

还有什么是最有效的。字符串匹配算法（如精确字符串匹配算法中的 boyer-moore）？

非常感谢任何见解/建议。提前谢谢了

我整晚都在想办法解决这个问题，但我想我对 .Net Framework 的了解并不那么深入，而且问题并不完全是谷歌，但如果我能在正确的方向上点头，我我确信我可以以一种或另一种方式实现它。

我希望能够声明一个用自定义属性装饰的属性，如下所示：

然后不知何故 - 这是我无法弄清楚的部分 - 用一段自定义代码替换自动生成的 getter 实现，例如：

我不确定该怎么做的主要事情是替换get的自动实现。

首先想到的是PostSharp，但这是一个比我关心的更复杂的依赖项。我更喜欢一种不使用附加到构建的后处理来编码它的方法（我认为这就是 PostSharp 无论如何都会下沉它的钩子的要点）。

我不太确定的另一部分是如何检索传递给 ReplaceWithExpressionFrom 属性的特定实例化的类型参数（它装饰我要替换其主体的属性；换句话说，我如何获取 typeof （SomeOtherClass），我正在编码获取身体替换）。我计划从 IExpressionHolder 的具体实例缓存已编译的表达式，因为我不想在每次检索属性时都这样做。

我认为这必须成为可能。至少我认为我应该能够在程序集中搜索任何用该属性装饰的方法并以某种方式代理该类或只是替换 IL 或 .. 什么？而且我想让集成尽可能顺利，所以如果这可以在不显式调用注册或初始化方法的情况下完成，那将是非常棒的。

谢谢！

我想拥有可以用我自己的自定义属性装饰的属性获取器和方法，并根据该属性的存在用不同的实现替换方法主体。此外，不同的实现将需要知道赋予自定义属性的构造函数参数，该属性在其中装饰方法。

这显然可以使用 AOP 来完成，比如 PostSharp 或 LinFu，但我想知道是否有一种方法可以做到这一点，它不涉及构建后处理步骤，因为添加它会使项目变得比我更喜欢的复杂化。

我的老师要求我们为这个问题实施一个动态编程解决方案，但我认为一个不存在，因为我无法使用谷歌找到它。

无论如何，给定一个图表和 ak，比如 3，你必须从中找到 3 个最好的 MST。如果该图没有 k 个子树，则可以多次返回同一棵树或次优树。

我实在想不出解决办法。

假设构建了字典单词的一般 Trie，那么在遍历期间检查 4 种拼写错误的最佳方法是什么 - 替换、删除、转置和插入？

一种方法是找出给定单词 n 个编辑距离内的所有单词，然后在 Trie 中检查它们。这不是一个坏选择，但这里更好的直觉似乎是使用动态编程（或递归等效）方法来确定在遍历期间修改单词后的最佳子尝试。

欢迎任何想法！

PS，会欣赏实际的输入，而不仅仅是答案中的链接。

我只是无法掌握dp。我知道我要做什么，但无法实现它。例如，来自“Codechef”的这个练习问题

http://www.codechef.com/problems/MIXTURES/

如果我认为混合物 i 到 j 的最小烟雾为 m[i,j]

然后

它是否正确？以及如何不断更新 diff k 的混合颜色，然后在下一个 k 恢复为原始颜色？

我想将域名分解为组成词和数字，例如

iamadomain11.com = ['i', 'am', 'a', 'domain', '11']

我该怎么做呢？我知道可能有多组可能，但是，我目前还可以，只获得一组可能性。