一个有趣的问题是为树(不一定是二进制的)中的每个节点分配标签(0,1或2)，其中父-子对不能具有相同的标签。此外，我们需要最大化所有标签的总和，即使用尽可能少的0。返回所使用的0标签的最小数目。一些叶节点已经被预先标记。我们不能改变这些标签。如果无法分配标签，例如，一个父节点的子节点预先标记了所有三个标签，则返回负无穷大。
我正在尝试动态规划。一种可能的递归是，OPT(v)返回用于标记v的子树的0的个数，我们从整个根开始。当向下递归树时，尝试将每个v的子节点标记为0、1和2(通过操作每个节点中的v.label字段)，并查看哪个选项返回0的最小值。如果我们到达底部，一个叶节点已经被预先标记，我们不能探索所有的标签，只能使用给定的标签。如果叶节点没有预先标记，则尝试每个标签，如上所述。树本身可以用作我的记忆结构，其中标签存储在每个节点的.label字段中。但是我不确定如何显式地写出递归式，特别是对于递归的情况，当我为当前节点的每个子节点探索所有可能的标签时。我不知道如何表示这个组合并求它的最小值。基本情况相当简单，如果叶子标记为0，可能返回1，否则返回0。
你的主意看起来不错。只有一件事需要改进:记忆不应该只关注一个标签值，而应该关注所有3个标签值(0,1和2)。对于每个标签，您将(每个节点)记住当该标签分配给它时，该节点树(其中它是根)中零的最小数量。
然后，根据您为父节点所做的选择，您将查看剩下的两个可能的标签，并选择链接到它的0数量最少的标签。
对于下面的实现，我使用了这个树作为示例:
*
/
* * ___
/| /
1 * * 2 * *
/
* 2 2
/|
2 * 0
星号表示没有标签的节点。
所以算法会从根开始暂时赋值为0，然后看看这给子节点留下了什么影响和可能性。然后对每个子节点遍历它可能具有的值(不为零)，…然后递归到树的更深处，每次都回溯——记录0个标签的计数——并继续使用节点的下一个可能的标签(并再次沿着树向下移动，除非有可用的记忆)。
对于上面的例子，我们可以看到一个最优的标签是:0
/
2 1 ___
/| /
1 1 1 2 0 0
/
1 2 2
/|
2 2 0
根节点和它的左子节点可以交换值——这无关紧要。结果是4个零。
实现如下:
// Main algorithm:
function triple(node, parentLabel=-1) {
let choices = node.label !== undefined ? [node.label] : [0,1,2];
let minCount = Infinity;
for (let label of choices) {
if (label === parentLabel) continue; // We cannot use same label as parent has
let count = node.memo[label]; // Already memoized?
if (count === undefined) { // No...
count = 0;
for (let child of node.children) {
count += triple(child, label); // recur
if (count >= minCount) break; // not better...
}
node.memo[label] = count;
}
if (label === 0) count++; // Count the zero
if (count < minCount) minCount = count; // better!
}
// Minimum number of 0-labels if parent has the given parentLabel
return minCount;
}
class Node {
constructor(label, ...children) {
this.label = label;
this.children = children;
this.memo = [undefined, undefined, undefined];
}
}
// Short-cut function for creating a Node instance with or without label
function N(...children) {
let label = undefined;
if (typeof children[0] === "number") { // first argument is a label
label = children.shift(); // extract first argument
}
return new Node(label, ...children);
}
// Demo
let tree = N(
N(
N(1), N(), N()
),
N(
N(2),
N(
N(
N(2), N(), N(0)
),
N(2)
),
N(
N(2)
)
)
)
console.log("input tree:");
console.log(tree);
let count = triple(tree);
console.log("Number of zeroes:", count);当没有有效的标签时，此实现将返回Infinity。