algorithm - 给定 n 个苹果卖掉的最大利润

Question

给定要出售的 n 个苹果和一个包含 n 个整数“price”的数组，其中 price[i] 表示可以出售 i+1 个苹果的价格。计算我们可以通过在任何地方出售 n 个苹果产生的最大收入我们可以选择的组合。

示例:给定 8 个苹果和价格数组如下:-

{1,5,8,9,10,17,17,20}
i.e.price of 1 apple = $1
total selling price of 2 apples = $5, etc.

销售 2 + 6 个苹果，总计 5 + 17 = 22 美元将产生最大收入。

我有一个简单的递归解决方案，但想知道我们可以实现的最佳时间复杂度是多少？是否有应用动态编程或记忆化的范围？

谢谢!

Answer 1

定义

让dp[k]表示卖出利润k苹果以最佳方式

让profit[k]引爆销售利润k一次吃苹果。

递归关系

很明显，dp[0] = 0 .

那么我们可以定义一个递归关系如下:

dp[k] = max{dp[i] + profit[k - i]}, where 0 <= i < k

你对计算感兴趣dp[n] .

结论

您可以使用自下而上的方法或内存轻松实现它，这两种方法都非常简单。

这个解决方案的时间复杂度是O(n^2) ，因为计算 dp 中的单个条目数组需要 O(n)时间。