问题标签 [bottom-up]

将经典楼梯问题考虑为“戴维斯在他的房子里有许多楼梯，他喜欢一次爬每一个楼梯 1、2 或 3 级。作为一个非常早熟的孩子，他想知道有多少种方法可以到达楼梯顶。”

我的方法是使用带有递归的记忆作为

我想到的问题是，这个解决方案是自下而上还是自上而下。我的处理方法是，因为我们一直向下计算上 N 个值（想象一下递归树）。我认为这是自下而上的。这个对吗？

您好，我一直在研究https://leetcode.com/problems/2-keys-keyboard/submissions/并遇到了这个动态编程问题。

您从空白页上的“A”开始，n完成后您会得到一个数字，您应该n在页面上有时间“A”。问题是您只允许复制 2 次操作（并且您只能复制页面上当前 A 的总数）并粘贴 -> 找到在n页面上获得“A”的最小操作数。

我编写了以下算法来解决这个问题，但我很难分析它的时间复杂度。

这是代码：

所以我的直觉说这个算法介于两者之间O(n^2)，O(nlogn)因为在第二个循环中我们比“更快”，O(n)但是由于每次迭代之间步长d不会加倍，所以O(n)对于第二个循环来说仍然有点......

我不确定如何分析那个，欢迎任何帮助。

我们得到一根长度为 n 英寸的棒。您可以将其切割成整数长度的不同部分。您的目标是尽可能获得所有零件长度的最大乘积。你必须至少剪一次。假设绳子的长度超过 2 米。参考：https ://www.geeksforgeeks.org/maximum-product-cutting-dp-36/

其他参考：切杆最大化利润的算法

我想使用二维表使用自下而上的动态编程来做这个问题。

假设我们的长度为 5。

每个单元格表示我们在给定长度的杆和指定的切割次数下可以获得的最大产品，以及切割后剩余的最大长度。

例如，假设我们需要用切割数 2 和杆长度等于 4 填充单元格。我假设每个单元格除了存储给定长度的最大乘积外，还将存储切割后剩余的最大长度。

在切割长度为 4 后，我们得到最大乘积 4，因为我们将左侧部分切割为 2，右侧部分切割为 2。我们存储两个数字：最大乘积为 4，最大乘积为 2。当我们在单元格 (2, 4) 时，我们可以进行切割，也可以不切割。如果我们不进行切割，那么我们查看当前行。我们循环遍历每个长度。在这种情况下，我们循环长度为 2 和长度为 3。如果长度为 2，则剩余的 4-2=2 并乘以得到 4。然后我们对 3 执行相同操作以获得剩余长度为为 1 并将其乘以 2 得到 2。

另一种选择是进行剪切，然后我们需要查看上排。我们再次从该行的开头循环。然后我们选择最大值。

我的问题是我必须每次循环遍历所有列，即从左到当前单元格，这将使时间复杂度为 O(n^3)。

有没有办法在 O(n^2) 中做到这一点，而不是使用 2D 表？

我正在为我们公司开发一个 BI 系统，从头开始，目前，我正在设计一个数据仓库。我对此完全陌生，所以有很多我不太了解的东西，所以我需要听到更多关于这方面的见解。

我的问题是：

1) 在我们的源系统中，有名为“Booking”和“BookingAccess”的表。预订表保存预订的数据，例如入住时间和退房时间、预订日期、预订编号、预订总额。

而在 BookingAccess 中，它保存与预订相关的外键，例如 bookerID、customerID、processID、hotelID、paymentproviderID 和该预订的当前状态。Booking 和 BookingAccess 具有 1:1 的关系。

我们的源系统是关于检查这些预订的有效性，这些预订不是我们的。我们从其他来源收到这些预订信息，为他们外包上述流程。总金额只是我们需要验证的预订信息，它们不是我们业务的一部分。BookingAccess 表中保留的预订的当前状态是我们系统中该预订的当前状态，可以是“处理中”或“已完成”。

根据我从 Ralph Kimball 那里读到的内容，在这种情况下，“Booking”是维度表，而 BookingAccess 应该是事实。我觉得 BookingAccess 有点像[累积快照表]，我应该在其中跟踪预订“处理”和预订“完成”的时间。

我做对了吗？

2）在“Booking”表中，还有一个外键叫做“ImportID”。此键链接到名为“导入”的表。此“导入”表保存已导入我们系统的文件的历史记录（这些文件包含将写入“预订”表的预订），包括文件名、导入日期、导入的总预订......

从我的角度来看，这显然是一个事实表。

但问题是，“导入”表和“预订”表具有一对多的关系（“导入”表中的 1 个 ImportID 可以有 1、2 个或更多记录，它们在“预订”表中具有相同的 ImportID ）。这与事实表的想法相悖，事实表坚持事实和维度之间的关系必须是多对一的，事实总是在多方面。

那么我应该使用什么方法来解决这种情况呢？我正在考虑使用桥接表来解决这个问题。但我不知道这是否是一个好习惯，因为“导入”表中有很多记录，所以我必须创建一个大的桥表来涵盖所有这些。

3）我应该将包含关系和信息混合的表（来自源系统）与仅包含关系的事实表和仅包含信息的维度表分开吗？（例如，源系统中名为“客户”的表。该表包含客户名称、客户地址和客户类型 ID、客户父 ID 等内容。）

我问这个是因为我觉得如果我使用 BI 工具来分析事物（例如，分析 customertypeid = 1 的客户数量），如果没有涉及事实表，我觉得这有些奇怪。

或者我应该把它当作一个单纯的维度表并使用雪花模式？但这会导致我们的数据仓库中混合使用星型模式和雪花模式。这是正常的吗？我已经阅读了一些官方资料（很可能是 Oracle），指出应该尽量避免使用和混合雪花模式。但微软等一些消息人士称，这是非常正常的。甚至Advanture Work Data Warehouse 示例数据库也使用这种方法。

或者我应该对“客户”表中的每个关系进行反规范化吗？但我认为这不是一个好方法，因为它会使 Customer 包含很多列，并且很难跟踪“DIM_Customer”表中每一行的历史记录。例如，如果“客户”表的任何关系发生任何变化，则需要更新整个“DIM_Customer”表。

关于数据仓库，我还有很多问题。我几乎独自一人使用它，没有任何帮助或顾问。如果我犯了任何不便或错误，请原谅我。

我正在使用底部弹出库并显示高达视图 1/3 高度的弹出窗口，我想从该控制器推送新屏幕。问题：- 当我尝试打开控制器时，它也显示高达 1/3 的高度，因为我声明了弹出窗口的导航高度。

我想全屏打开控制器

请查看底部弹出库以进一步可视化

假设我们使用记忆化（自上而下方法）或制表法（自下而上）使用动态编程来处理两个字符串之间的最长公共子序列问题。

我的问题是，可以更改这两种方法中的哪一种以另外返回最长的公共字符串（超出其长度）？我的意思是：

两种方法都可以改变来实现这一点还是取决于问题？

[编辑]
我的直觉是，记忆方法可以“轻松”更改，以便跟踪实际解决方案。但是，鉴于制表方法中的“表格内容”，我看不到一种简单的方法（或一般方法）来回溯解决方案。请尽可能笼统地回答（不是专门针对 LCS 问题）。

请原谅我的天真，因为我没有太多的编程经验。在谷歌搜索一个不相关的问题时，我偶然发现了这个：

https://www.geeksforgeeks.org/find-number-of-solutions-of-a-linear-equation-of-n-variables/

我完全理解第一段（效率极低）的代码。但第二个：

让我困惑。我的问题是：为什么第二个程序要计算非负整数解的数量？

我写了几个例子，包括文章中给出的例子，我知道它确实做到了这一点。而且我了解它是如何填充列表的。但我不明白为什么会这样。

请原谅对某些人来说一定是一个无知的问题。但是我很想理解这个逻辑，因为我认为这样一个小片段非常聪明——它能够回答像“存在多少非负整数解”这样的一般问题（对于一些一般方程）。

我必须使用动态编程解决一个经典的分区问题。我有一个正整数数组作为输入，其中n是整数的数量，s是这些整数的总和，我需要找到可以使用输入元素构造的两个集合之间的最小差异。我还需要输出一个名为“所有权”的布尔数组，其大小与输入数组相同，它提供了元素是否属于第一个或第二个最优集的信息。例如，如果所有权数组中的第 i 个值为 true ，则输入数组的第 i 个元素属于第一个集合。

我的程序使用自下而上的方法找到最小的差异。该任务要求程序的内存复杂度为θ ( s )，因此我不使用经典方法中大小为 n*s 的二维数组，而是仅使用该数组的两行。在第一行中，我保留了之前处理过的行，因此我可以根据之前的解决方案填充第二行。

问题是，通过这种内存优化，我不确定应该如何填充所有权数组。

我知道可以使用 n*s 数组中的回溯来检索集合元素。但是，由于任务限制，我无法使用该方法，也不知道如何有效地构建所有权表。

有没有一种方法可以有效地找到哪些元素属于这两个最优集合中的哪一个，并且在自下而上的方法中 受到内存复杂度θ ( s ) 和时间复杂度O (n*s) 的约束？

我当前的 C# 代码：

所以我读到，当你一个一个地获取元素时，你应该使用自下而上的堆构造而不是自上而下的 heapify，但是如果我每次添加新元素时都使用 heapify 算法，基本上从 n/ 开始做同样的事情每次我在数组中添加一个元素时，2 对 1 heapify(i) 的事情，这种方法在使用 bittom up heap 构造方面有什么缺点，时间复杂度是多少

我正在阅读这篇关于常见算法问题的LeetCode 文章，“最长公共前缀”。他们展示了几种不同的方法，但我的问题仅与“分而治之”有关。它的示例显示了您经常在各处的书籍和博客中看到的典型递归自上而下方法。

看着这个让我想到我应该能够“迭代地”和“自下而上”地做到这一点。类似于自下而上的合并排序方法。所以这就是我结束的地方：

所以我的问题是：这仍然被认为是“自下而上”和“分而治之”吗？我认为可以安全地假设立即从叶子开始（自下而上的部分）只需一次处理两个元素，因为它通过数组一次（“划分”......但也是“征服？ ”）。这里的堆栈当然与递归方法中的调用堆栈发挥相同的作用。虽然，队列也可以，这是我认为我已经离开这里的另一个原因。

如果这不是“自下而上”和“分而治之”的正确应用，这是否至少应用了我不知道的其他一些理论？