Maximum Points After Collecting Coins From All Nodes - DP - Recursion w/ Memoization [JS]

Description 

Solution: DP - Recursion w/ Memoization

For the second type of operation (floor(coins[i] / 2)), instead of physically updating all the subtree values, we can pass down the number of reductions we need to perform on the subtree nodes.

Memoize each dp(node, reductions), where dp(node, reductions) is the maximum points for the subtree rooted at node node, with reductions division 2 reductions that need to be performed on the current node value.

For each dp(node, reductions, parent), first we need to get the updated node value (divide coins[node] by the appropriate number of reductions).
We then have two choices:

1. Take coins[node] - k.
2. Take Math.floor(coins[node] / 2), and increase reductions by 1 for all child nodes.

Return the maximum points in these two situations.

Note:

• We can observe that the maximum number of reductions needed to turn the maximum coin value (10^4) into 0 is 14.
• There is no point performing more reductions once the node value becomes 0.

Time Complexity: O(n * 15)
Space Complexity: O(n * 15)

var maximumPoints = function(edges, coins, k) {
  let n = edges.length + 1, graph = Array(n).fill(0).map(() => []);
  for (let [a, b] of edges) {
    graph[a].push(b);
    graph[b].push(a);
  }
  let memo = Array(n).fill(0).map(() => Array(15).fill(null));
  return dp(0, 0, -1);
  
  function dp(node, reductions, parent) { // maximum number of coins collected with root being `node` 
    if (memo[node][reductions] !== null) return memo[node][reductions];
    
    let nodeValue = coins[node] >> reductions;
    let option1 = nodeValue - k, option2 = Math.floor(nodeValue / 2);
    for (let child of graph[node]) {
      if (child === parent) continue;
      option1 += dp(child, reductions, node);
      option2 += dp(child, Math.min(14, reductions + 1), node);
    }
    return memo[node][reductions] = Math.max(option1, option2);
  }
};