A city has N buildings, connected by streets that form a tree. We want to light all streets in the city. This can be done by placing a light at any building. When a light is at building B, all streets out of B are lighted. Your task is to light the city using the minimum number of lights. Design a Dynamic Programming algorithm to find the minimum number of lights needed. Your input is an undirected tree on N vertices, representing the buildings (vertices) and streets (edges). Your output should be the minimum number of lights needed to light the city.

I think there will be 2 states to this DP, the building can be lighted or not lighted. And the recurrence relation will be different for both. I am struggling to find the logic behind the recurrence relation in this question. Can someone help with this?

CodePudding user response：

To solve this problem using dynamic programming, we can break it down into smaller subproblems. For each building, we can consider whether or not it is a good idea to place a light at that building. If we place a light at a building, we can light all of the streets that originate from that building. If we do not place a light at a building, we need to ensure that the streets originating from that building are already lit by lights placed at other buildings.

We can use a two-dimensional array to store the minimum number of lights needed for each subproblem. The first dimension of the array will represent the building we are considering, and the second dimension will represent whether or not that building has a light. The value in each cell will be the minimum number of lights needed to light the city starting from that building and considering whether or not it has a light.

To fill in the array, we can start by considering the leaf nodes in the tree (buildings with no children). For a leaf node, if it has a light, it is sufficient to light the city (since there are no streets originating from that building). If it does not have a light, it is not possible to light the city.

We can then consider the non-leaf nodes in the tree. For each non-leaf node, we need to consider two cases:

1. The building has a light: In this case, we need to find the minimum number of lights needed to light the city starting from each of the building's children, assuming that the children do not have lights. We can find this by looking up the values in the array for each of the building's children and summing them up.

2. The building does not have a light: In this case, we need to find the minimum number of lights needed to light the city starting from each of the building's children, assuming that the children either have lights or are already lit by lights placed at other buildings. We can find this by looking up the minimum value in the array for each of the building's children.

Once we have filled in the entire array, we can look at the value in the cell at position (1, 0) to find the minimum number of lights needed to light the entire city. This value will represent the minimum number of lights needed to light the city starting from the root node of the tree and assuming that the root node does not have a light.

In summary, the steps to solve this problem using dynamic programming are as follows:

1. Initialize a two-dimensional array to store the minimum number of lights needed for each subproblem.
2. Fill in the leaf nodes of the tree:

• If the leaf node has a light, set the value in the array to 1.
• If the leaf node does not have a light, set the value in the array to infinity.

3. Consider the non-leaf nodes in the tree, starting from the leaf nodes and working towards the root:
   • For each non-leaf node, consider two cases:
     • If the building has a light, find the minimum number of lights needed to light the city starting from each of the building's children, assuming that the children do not have lights. Set the value in the array to the sum of the values found for each child.
     • If the building does not have a light, find the minimum number of lights needed to light the city starting from each of the building's children, assuming that the children either have lights or are already lit by lights placed at other buildings. Set the value in the array to the minimum value found for each child.
4. Return the value in the cell at position (1, 0) in the array, which represents the minimum number of lights needed to light the entire city starting from the root node of the tree and assuming that the root node does not have a light.

Here is some sample pseudocode that implements this algorithm:

function minimumLights(tree):
  // Initialize a two-dimensional array to store the minimum number of lights needed for each subproblem
  let dp = new Array(tree.numNodes   1)
  for (let i = 1; i <= tree.numNodes; i  ) {
    dp[i] = new Array(2)
  }

  // Fill in the leaf nodes of the tree
  for (let i = 1; i <= tree.numNodes; i  ) {
    if (tree.isLeaf(i)) {
      dp[i][0] = infinity  // Cannot light the city if the leaf node does not have a light
      dp[i][1] = 1         // Can light the city if the leaf node has a light
    }
  }

  // Consider the non-leaf nodes in the tree, starting from the leaf nodes and working towards the root
  for (let i = tree.numNodes; i >= 1; i--) {
    if (!tree.isLeaf(i)) {
      // If the building has a light, find the minimum number of lights needed to light the city starting from each of the building's children, assuming that the children do not have lights
      dp[i][1] = 0
      for (let child of tree.children(i)) {
        dp[i][1]  = dp[child][0]
      }

      // If the building does not have a light, find the minimum number of lights needed to light the city starting from each of the building's children, assuming that the children either have lights or are already lit by lights placed at other buildings
      dp[i][0] = infinity
      for (let child of tree.children(i)) {
        dp[i][0] = min(dp[i][0], dp[child][0], dp[child][1])
      }
    }
  }

  // Return the minimum number of lights needed to light the entire city starting from the root node of the tree and assuming that the root node does not have a light
  return dp[1][0]