问题描述 在一个神秘的竞技场中，勇敢的探险者小青拥有两个宝箱：一个宝箱里装满了 n 个金银珠宝的数值，另一个则是一个包含 m 个神秘符文的序列。小青面临着一个挑战：在接下来的 m 轮中，他必须在这两者之间做出明智的选择，以获得最高的财富。 在每一轮（第 i 轮）中，小青可以选择从宝箱的最上面或最下面取出一个珠宝 x。然后，他会将这个珠宝的价值乘以对应的符文 c[i]，并把结果累加到他的总财富中。被取出的珠宝将从宝箱中消失，接着小青会继续下一**作，直到完成 m 轮。 你的任务是帮助小青计算，在完成 m 轮挑战后，他可以获得的最高财富是多少。 输入： stones：宝箱中n个金银珠宝的数值 c：m个神秘符文 约束条件： 时间限制：3s stones 和 c序列大小的数据范围为 1 ≤ m ≤ n≤ 2000，并且 -1000 ≤ stones[i], c[i]≤ 1000 测试样例 样例1： 输入：stones = [-3, 4, 5], c = [2, -1, 3] 输出：25 样例2： 输入：stones = [6, -7, 1], c = [4, -3] 输出：45

思路： 这是一个典型的动态规划问题。 我们可以用一个二维数组dp来记录小青在每一轮中所能获得的最大财富。 dp[i][j]表示小青在第i轮取出第j个珠宝时所能获得的最大财富。 对于第i轮取出的珠宝x，有两种情况： 1. 如果取出的是最上面的珠宝，即dp[i][j] = dp[i-1][j] + stones[j] * c[i]。 2. 如果取出的是最下面的珠宝，即dp[i][j] = dp[i-1][j-1] + stones[j] * c[i]。 小青在第i轮中的最大财富就是这两种情况中的较大值。 为了使得边界情况也能适用于上述状态方程，我们可以在stones和c的前面分别插入一个0，即stones = [0] + stones，c = [0] + c。 算法流程： 1. 初始化二维数组dp，大小为(m+1)×(n+1)，并将其所有元素初始化为0。 2. 将stones和c的前面插入一个0。 3. 对于i从1到m， j从1到n，进行如下操作： - 如果j == 1，即取出的是最上面的珠宝，则dp[i][j] = dp[i-1][j] + stones[j] * c[i]。 - 如果j == n，即取出的是最下面的珠宝，则dp[i][j] = dp[i-1][j-1] + stones[j] * c[i]。 - 否则，dp[i][j] = max(dp[i-1][j] + stones[j] * c[i], dp[i-1][j-1] + stones[j] * c[i])。 4. 返回dp[m][n]，即最高财富。 时间复杂度分析： 由于需要遍历m×n个状态，因此时间复杂度为O(mn)。 [2024-12-07 11:39:39 | AI写代码神器 | 695点数解答]