由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 问个color tree的DP问题
相关主题
问个guangyi的面试题插入节点到complete binary tree的末尾
问一个很简单的suffix tree问题。请指点。请教这么一个题:BST maximum sum path
问一个题 house paintL家的面试体验让人有些无语
a question regarding finding all paths with a common sumUni_value subtree problem
rebuild a tree from inorder and level order二叉查找树中两个节点被错误的交换了,如何有效找出他们
关于inordertraversal 的iterative waycareercup 150 4.1 balanced tree 有错?
least common ancestor的疑惑贴个树的老题目
问两道facebook面试题recovery BST 不考虑相同值的情况么?
相关话题的讨论汇总
话题: dp话题: color话题: leaf话题: given
进入JobHunting版参与讨论
1 (共1页)
d*******i
发帖数: 117
1
"
Suppose we are given a rooted tree T with n leaves and m non-leaf nodes.
Each leaf is colored with one of k < n given colors, so several leaves can
have the same color. We need to color each interior node of T with one of
the k given colors to maximize the number of edges whose (two) endpoints
are colored the same color.
We can solve this with a DP algorithm that runs in O(mk) time. Let V (v,
i) denote the optimal solution value when the problem is applied to the
subtree rooted at node v, and v is required to be given color i. Let V (v)
denote the optimal solution value when the problem is applied to the
subtree rooted at node v, and there is no restriction on which of the k
colors v can be.
a. Using that notation, develop recurrences for this problem, and explain
the correctness of your recurrences.
b. Explain how the recurrences are evaluated (solved) in an efficient DP
way.
c. Show that the time bound for your DP is O(mk).
m**q
发帖数: 189
2
设f(v, i)表示节点v的parent节点设为x颜色时,以v为根的子树中
拥有的两个端点同色的边的个数(包括v和v的parent之间的边)
则:所求为min {f(root, i)} (1<= i <= k)

f(v, i) = sum{f(c,i)} (v is root, c is child of v)
min ( 1 + sum {f(c, i)}, { min (sum {f(c, j)}), j!= i })
(v is non leaf, c is child of v)
1 (v is leaf && color(v) == i)
0 (v is leaf && color(v) != i)
Note here v is a pointer, you can create a hash table with v as key
and each v is associated with an int identifier, so we can use an
array like f[x, i] (1<= x <=m, 1<= i <=k). Complexity is O(km)

nodes.
can
of
endpoints
(v,
the
(v)

【在 d*******i 的大作中提到】
: "
: Suppose we are given a rooted tree T with n leaves and m non-leaf nodes.
: Each leaf is colored with one of k < n given colors, so several leaves can
: have the same color. We need to color each interior node of T with one of
: the k given colors to maximize the number of edges whose (two) endpoints
: are colored the same color.
: We can solve this with a DP algorithm that runs in O(mk) time. Let V (v,
: i) denote the optimal solution value when the problem is applied to the
: subtree rooted at node v, and v is required to be given color i. Let V (v)
: denote the optimal solution value when the problem is applied to the

1 (共1页)
进入JobHunting版参与讨论
相关主题
recovery BST 不考虑相同值的情况么?rebuild a tree from inorder and level order
Amazon 打印给定node距离最近的K个nodes关于inordertraversal 的iterative way
问一道google面经least common ancestor的疑惑
largest bst 解法不理解的地方问两道facebook面试题
问个guangyi的面试题插入节点到complete binary tree的末尾
问一个很简单的suffix tree问题。请指点。请教这么一个题:BST maximum sum path
问一个题 house paintL家的面试体验让人有些无语
a question regarding finding all paths with a common sumUni_value subtree problem
相关话题的讨论汇总
话题: dp话题: color话题: leaf话题: given