SDE 位置的编码问题 - 与 DP 有关

Question

我的朋友做了一个测试，他得到了这个问题。我尽力解决这个问题，但没能走多远，有人可以提供解决这个问题的方法吗？

问题陈述

输入?输出测试用例

Answer 1

您的第一步是确定一组给定的输入是否提供任何解决方案。不可能有解决方案的一种方法是，如果两个连续的盒子每个都只有一种颜色。它使用数字，但我喜欢用颜色来思考，所以说一个框是红色的，下一个框也是红色的。不行，条件不成立

但情况变得更糟 - 如果一个框是红色的，下一个框是红色和橙色的，而下一个框只是橙色的。好吧，如果你必须在第一个盒子里拿红色，那么你必须在第二个盒子里拿橙色。但是第三个盒子里的橘子你也一定要拿！

您首先构建这些框的矩阵并跟踪其中 gem 的内容，以及其中哪些 gem 有资格被选中。遍历矩阵，您将每个框只取一种颜色，并排除两边的框具有该颜色。然后再次迭代，因为现在有些框现在只有一种颜色（如上例中的 red/orange）。如果您有一个没有有效选择的框，那么您就完成了。我可能遗漏了一些极端情况，但希望你现在明白了。

这个概念实际上与数独解算器的工作方式非常相似 - 考虑看看那些以获取灵感。

如果每个框都有一个有效的选择，那么就该针对价值进行优化了。我将从确定每个盒子中价值最大的钻石开始。显然，您想尽可能多地选择它。天真的算法可能只是在单次传递中迭代这些框，选择最高的 gem，或者如果最高的 gem 被最后一个框采用，则选择第二高的 gem。更高级的算法可能会提前查看接下来的几个框（或整个集合的其余部分？）以确定哪个是最佳组合。可能有一些我没有看到的更高级的处理方法，但同样，这应该为一些感兴趣的团体指明正确的方向。

Answer 2

让我们定义一个函数 f(i,j)，它给出从第 i 个盒子 (1,2....i) 中取出钻石的最大值，我们从第 i 个盒子中挑选钻石 j。

那么你的问题的答案就是 max(f(n,j)) 其中 j=1,2,...bn 其中 bn 是盒子 n 中的钻石数量。

对于每个盒子，我们需要尝试挑选一颗钻石，并尝试从前一个盒子中挑选一颗颜色不相似的钻石来最大化价值，因此公式为：

f(i,j) = Vj + max(f(i-1,k)) // diamond k should not have the same color as diamond j

要以有效的方式计算 max(f(i-1,k))，您可以跟踪每个框 i 的函数 f(i,j) 的最大 2 个值：
max1 = f(i,j1)
max2 = f(i,j2)

这是一个伪代码：

max1 = -1;
max2 = -1;

for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= diamonds_of_box_i; j++) {
        f[i][j] = -1;
        if (max1.color != diamond[j].color && max1 != -1)
            f[i][j] = max(f[i][j], max1) + Vj;

        if (max2.color != diamond[j].color && max2 != -1)
                f[i][j] = max(f[i][j], max2) + Vj;
        }

        max1 = max2 = -1;
        for (int j = 1; j <= diamonds_of_box_i; j++) {
            if (f[i][j] > max1) {
                max2 = max1;
                max1 = f[i][j];
            }
            else if (f[i][j] > max2) {
                max2 = f[i][j];
            }
        }
    }

    for (int j = 1; j < diamonds_of_box_n; j++){
        if (f[n][j] > res)
            res = f[n][j];
    }

    print(res);

SDE 位置的编码问题 - 与 DP 有关

Coding Question for SDE Positon - Related to DP

dynamic-programming

data-structures