03 — DP Advanced

DP on Trees

Maximum Path Sum (Binary Tree)

function maxPathSum(root: TreeNode | null): number {
  let maxSum = -Infinity;
  
  function dfs(node: TreeNode | null): number {
    if (!node) return 0;
    
    const left = Math.max(0, dfs(node.left));   // Ignore negative paths
    const right = Math.max(0, dfs(node.right));
    
    // Path through this node (potential answer)
    maxSum = Math.max(maxSum, left + node.val + right);
    
    // Return max single-side path (for parent to use)
    return node.val + Math.max(left, right);
  }
  
  dfs(root);
  return maxSum;
}

Tree Diameter

function treeDiameter(adj: number[][]): number {
  const n = adj.length;
  let diameter = 0;
  
  function dfs(node: number, parent: number): number {
    let max1 = 0, max2 = 0; // Two longest paths from node
    
    for (const child of adj[node]) {
      if (child === parent) continue;
      const depth = dfs(child, node) + 1;
      if (depth > max1) { max2 = max1; max1 = depth; }
      else if (depth > max2) { max2 = depth; }
    }
    
    diameter = Math.max(diameter, max1 + max2);
    return max1;
  }
  
  dfs(0, -1);
  return diameter;
}

Rerooting Technique

Compute answer for all nodes as root efficiently.

// Sum of distances from each node to all other nodes
function sumOfDistances(n: number, edges: number[][]): number[] {
  const adj: number[][] = Array.from({ length: n }, () => []);
  for (const [u, v] of edges) { adj[u].push(v); adj[v].push(u); }
  
  const count = new Array(n).fill(1); // Subtree size
  const ans = new Array(n).fill(0);
  
  // Pass 1: Root at 0, compute subtree sizes and ans[0]
  function dfs1(node: number, parent: number, depth: number) {
    ans[0] += depth;
    for (const child of adj[node]) {
      if (child === parent) continue;
      dfs1(child, node, depth + 1);
      count[node] += count[child];
    }
  }
  
  // Pass 2: Reroot — when moving root from parent to child:
  // ans[child] = ans[parent] - count[child] + (n - count[child])
  function dfs2(node: number, parent: number) {
    for (const child of adj[node]) {
      if (child === parent) continue;
      ans[child] = ans[node] - count[child] + (n - count[child]);
      dfs2(child, node);
    }
  }
  
  dfs1(0, -1, 0);
  dfs2(0, -1);
  return ans;
}

---

DP on Graphs

Shortest Path in DAG (DP approach)

// Topological order → relax edges
function shortestPathDAG(adj: [number, number][][], n: number, src: number): number[] {
  const dist = new Array(n).fill(Infinity);
  dist[src] = 0;
  const order = topologicalSort(adj, n);
  
  for (const u of order) {
    if (dist[u] === Infinity) continue;
    for (const [v, w] of adj[u]) {
      dist[v] = Math.min(dist[v], dist[u] + w);
    }
  }
  return dist;
}

Number of Paths in DAG

function countPaths(adj: number[][], n: number, src: number, dest: number): number {
  const dp = new Array(n).fill(0);
  dp[dest] = 1;
  const order = topologicalSort(adj, n).reverse(); // Reverse topo order
  
  for (const u of order) {
    for (const v of adj[u]) {
      dp[u] += dp[v];
    }
  }
  return dp[src];
}

---

Digit DP

Count numbers in range [L, R] satisfying some digit property.

// Count numbers from 0 to N with digit sum = S
// State: position, currentSum, tight (is current prefix = N's prefix?)
function countWithDigitSum(N: string, S: number): number {
  const n = N.length;
  const memo = new Map<string, number>();
  
  function dp(pos: number, sum: number, tight: boolean, started: boolean): number {
    if (sum > S) return 0;
    if (pos === n) return started && sum === S ? 1 : 0;
    
    const key = `${pos},${sum},${tight},${started}`;
    if (memo.has(key)) return memo.get(key)!;
    
    const limit = tight ? parseInt(N[pos]) : 9;
    let result = 0;
    
    for (let d = 0; d <= limit; d++) {
      result += dp(
        pos + 1,
        started || d > 0 ? sum + d : 0,
        tight && d === limit,
        started || d > 0
      );
    }
    
    memo.set(key, result);
    return result;
  }
  
  return dp(0, 0, true, false);
}

// Count in range [L, R]: f(R) - f(L-1)

---

Interval DP

Problems on contiguous intervals.

Matrix Chain Multiplication

// Minimum multiplications to multiply chain of matrices
// dims[i] = rows of matrix i, dims[n] = cols of last matrix
function matrixChain(dims: number[]): number {
  const n = dims.length - 1;
  const dp = Array.from({ length: n }, () => new Array(n).fill(0));
  
  // len = chain length
  for (let len = 2; len <= n; len++) {
    for (let i = 0; i <= n - len; i++) {
      const j = i + len - 1;
      dp[i][j] = Infinity;
      for (let k = i; k < j; k++) {
        dp[i][j] = Math.min(
          dp[i][j],
          dp[i][k] + dp[k + 1][j] + dims[i] * dims[k + 1] * dims[j + 1]
        );
      }
    }
  }
  return dp[0][n - 1];
}

Burst Balloons

function maxCoins(nums: number[]): number {
  const arr = [1, ...nums, 1];
  const n = arr.length;
  const dp = Array.from({ length: n }, () => new Array(n).fill(0));
  
  for (let len = 2; len < n; len++) {
    for (let left = 0; left < n - len; left++) {
      const right = left + len;
      for (let k = left + 1; k < right; k++) {
        dp[left][right] = Math.max(
          dp[left][right],
          dp[left][k] + dp[k][right] + arr[left] * arr[k] * arr[right]
        );
      }
    }
  }
  return dp[0][n - 1];
}

---

Key Takeaways

• DP on Trees: DFS post-order; return subtree info to parent; rerooting for all-root answers
• DP on Graphs: Works on DAGs; use topological order as DP iteration order
• Digit DP: Count numbers with digit properties; state = (position, property, tight)
• Interval DP: dp[i][j] = answer for subarray [i..j]; iterate by interval length
• These patterns appear in hard interview and competitive programming problems