问题标签 [bottom-up]

在这种方法中，计算较小的子问题并缓存结果，然后我们计算较大的子问题，我们使用缓存了较早计算值的表中较小子问题的已计算优化值。那么，这种方法是递归的还是迭代的？

（这个问题是关于数据提炼的策略和高级方法，而不是编程，所以如果它是题外话......提前抱歉，但我找不到更好的 stackexchange 社区）

因此，我们处于一个（典型）场景中，新数据由大量用户引入（自下而上的贡献），并由版主/管理员/受信任的用户定期提炼、纠正、分类和丰富（自上而下提炼）。

这种情况在网站中很常见（stackexchangetags就是一个很好的例子）

是否有“最佳策略”来最小化工作量并最大限度地提高数据质量？

这里有些疑问：

1. 强制数据通过验证过程或让它们填充系统（接受一定程度的不正确/不一致）并在出现时修复/丰富最流行的数据。
2. 自上而下用尽可能多的数据预填充系统，以预测自下而上的到达。
3. 帮助自下而上的条目与其他数据保持一致（自动完成和用户的意思框）

如果 A 列中有文本，在 B20 中有空单元格，我想获取 A20 上方第一个非空单元格的行号，没有 VBA。

我找到了一些带有“LOOKUP”功能的示例，但出现“DIV/0”错误。Perharps，因为我在 A 列中有文本而不是数字？

请问你能帮帮我吗 ？

1. 如果下一个输入符号没有转换（因为它没有前瞻），LR(0)-Parsers 会简单地减少它是否正确？
2. SLR(1)-Parsers 使用产品的 FOLLOW-Set 作为前瞻是否正确？
3. LR(1)-Parsers 使用 FIRST-，而不是FOLLOW-Set 作为前瞻，对吗？

closure明确使用的算法FIRST

再说一次，我对此感到困惑。

4.7.1 Canonical LR(1) Items龙书下段说：

因此，我们只需要对那些 [A → α·, a]是处于堆栈顶部状态的 LR(1) 项的输入符号 a 进行 A → α减少。此类 a 的集合将始终是FOLLOW(A)的子集，但它也可以是真子集，如示例 4.51 中所示。

对于“切杆”问题：

给定一根长度为 n 英寸的杆和一个价格数组，其中包含所有尺寸小于 n 的块的价格。确定通过切割杆并出售碎片可获得的最大值。[链接]

算法简介(CLRS) 第 366 页给出了这种自下而上（动态编程）方法的伪代码：

现在，我无法理解第 6 行背后的逻辑。为什么他们这样做max(q, p[i] + r[j - i])而不是max(q, r[i] + r[j - i])？由于这是一种自下而上的方法，我们将r[1]先计算，然后再r[2], r[3]...进行计算。这意味着在计算 r[x] 时，我们保证有 r[x - 1]。

r[x] 表示我们可以获得长度为 x 的杆的最大值（在将其切割以最大化利润之后），而 p[x] 表示长度为 x 的单根杆的价格。第 3 - 8 行计算r[j]j = 1 到 n 的值，第 5 - 6 行计算通过考虑所有可能的切割，我们可以卖出长度为 j 的杆的最高价格。那么，在第 6 行中使用 p[i] 而不是 r[i] 有什么意义呢？如果在我们将长度 = i 切割后试图找到一根杆的最高价格，我们不应该添加价格吗？ r[i] 和 r[j - 1]？

我已经使用此逻辑编写了 Java 代码，并且它似乎为我尝试过的许多测试用例提供了正确的输出。我是否错过了一些我的代码产生错误/低效解决方案的情况？请帮帮我。谢谢！

我需要帮助理解这一点。父列表中的元素是如何给出的——比如它指的是序列中前一个元素的哪个列表？我已经尝试对每个列表进行测试，但我仍然得到不同的父列表。如果这是一个愚蠢的问题，请提前道歉。

自下而上的技术在解决问题时看起来更容易一些（我的观点），但是它是否可以在我们使用自上而下方法的任何地方使用，或者是否有任何特定的实例可以或我们应该使用自下而上的技术？

我有一个递归算法，我在其中计算一些概率值。输入是一个整数列表和一个整数值，它表示一个常量值。

例如，p([12,19,13], 2)进行三个递归调用，它们是

p([12,19],0)和p([13], 2)

p([12,19],1)和p([13], 1)

p([12,19],2)和p([13], 0)

因为 2 可以分解为 0+2、1+1 或 2+0。然后每个调用都遵循类似的方法并进行其他几个递归调用。

我有的递归算法

我一直在尝试将其转换为自下而上的 DP 代码，但无法弄清楚我需要进行迭代的方式。

我写下了最终结果需要计算的所有中间步骤，很明显在递归调用的底部有很多重复。

我尝试创建一个预先计算值的字典，如下所示

并使用这些值而不是进行第二次递归调用p(listvals2, c2)，但就运行时间而言，它并没有多大帮助。

如何通过使用适当的自下而上的方法来提高运行时间？

到目前为止，我对自底向上解析的算法的理解是这样的。

1. 将令牌移入堆栈
2. 如果某些元素（包括顶部）可以通过某些生产规则减少，则从顶部检查堆栈
3. 如果元素可以减少，弹出并推动生产规则的左侧。
4. 继续这些步骤，直到顶部是开始符号，下一个输入是 EOF

所以用一个示例语法来支持我的问题，

S → aABe

A → Abc
A → b
B → d

如果我们输入字符串为

缩写$

我们将a在堆栈中移动，因为没有减少的生产规则a，我们移动下一个令牌b。然后我们可以找到一个生产规则A → b并减少b到A。

那么我的问题是这个。我们aA在堆栈上，下一个输入是b. 那么解析器如何判断我们是否归约b到A我们等待c来使用的规则A → Abc呢？

当然，减少b到A那个点会导致错误。但是解析器是如何知道我们应该等待的c呢？

如果我在学习时遗漏了什么，我很抱歉。

这是 DP 的一个普遍问题。我必须在仅由非相邻元素形成的数组中找到最大和。我看到了其他帖子，但我想使用动态编程来做到这一点，特别是自下而上的 DP。这是我的代码：

我在通过测试用例时遇到错误。尽管当我手动运行一个测试用例时，它的结果是正确的。实际输出与我获得的相同。但是测试系统给我的代码提供了不同的输出。

我在测试用例上手动测试了这段代码：3 5 -7 8 10，答案与实际输出匹配（=15），但测试用例没有通过。

请指出我做错的正确方向。