Implementing Advanced DP Patterns

function diameterOfBinaryTree(root) {
  let maxDiameter = 0;

  function height(node) {
    if (!node) return 0;
    let left = height(node.left);
    let right = height(node.right);
    maxDiameter = Math.max(maxDiameter, left + right);
    return 1 + Math.max(left, right);
  }

  height(root);
  return maxDiameter;
}

const generateSubsets = (nums) => {
  const n = nums.length;
  const result = [];
  
  for (let mask = 0; mask < (1 << n); mask++) {
    const subset = [];
    for (let i = 0; i < n; i++) {
      if (mask & (1 << i)) {
        subset.push(nums[i]);
      }
    }
    result.push(subset);
  }
  
  return result;
};

// Example usage:
console.log(generateSubsets([1, 2, 3]));
// Output: [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

const tsp = (dist) => {
  const n = dist.length;
  const dp = Array(1 << n).fill().map(() => Array(n).fill(Infinity));
  dp[1][0] = 0; // Start at city 0

  for (let mask = 1; mask < (1 << n); mask++) {
    for (let u = 0; u < n; u++) {
      if (!(mask & (1 << u))) continue;
      
      for (let v = 0; v < n; v++) {
        if (mask & (1 << v)) continue;
        
        const newMask = mask | (1 << v);
        dp[newMask][v] = Math.min(dp[newMask][v], dp[mask][u] + dist[u][v]);
      }
    }
  }

  // Find minimum cost to return to start
  let minCost = Infinity;
  for (let i = 0; i < n; i++) {
    minCost = Math.min(minCost, dp[(1 << n) - 1][i] + dist[i][0]);
  }

  return minCost;
};

// Example usage:
const distances = [
  [0, 10, 15, 20],
  [10, 0, 35, 25],
  [15, 35, 0, 30],
  [20, 25, 30, 0]
];
console.log(tsp(distances)); // Output: 80

import bisect

class ConvexHullTrick:
    def __init__(self, is_min=True):
        self.lines = []
        self.is_min = is_min

    def add_line(self, m, b):
        # Remove lines that are dominated
        while len(self.lines) >= 2:
            # Check if the last line is dominated
            if self.is_dominated(self.lines[-2], self.lines[-1], (m, b)):
                self.lines.pop()
            else:
                break
        self.lines.append((m, b))

    def query(self, x):
        # Binary search for the best line
        idx = bisect.bisect_left(self.lines, (x, float('inf')))
        if self.is_min:
            return min(m * x + b for m, b in self.lines)
        else:
            return max(m * x + b for m, b in self.lines)

    def is_dominated(self, line1, line2, line3):
        # Check if line2 is dominated by line1 and line3
        m1, b1 = line1
        m2, b2 = line2
        m3, b3 = line3

        # For min case: line2 is dominated if it's never better than the other two
        return (b2 - b1) * (m3 - m2) <= (b3 - b2) * (m2 - m1)

function matrixChainOrder(p) {
  const n = p.length - 1;
  const m = Array(n).fill().map(() => Array(n).fill(0));
  const s = Array(n).fill().map(() => Array(n).fill(0));

  for (let l = 2; l <= n; l++) {
    for (let i = 1; i <= n - l + 1; i++) {
      const j = i + l - 1;
      m[i][j] = Infinity;
      for (let k = i; k < j; k++) {
        const q = m[i][k] + m[k+1][j] + p[i-1] * p[k] * p[j];
        if (q < m[i][j]) {
          m[i][j] = q;
          s[i][j] = k;
        }
      }
    }
  }

  return m[1][n];
}

// Example usage:
const dimensions = [10, 20, 30, 40];
console.log(matrixChainOrder(dimensions)); // Output: 9000

function knuthOptimization(p) {
  const n = p.length - 1;
  const dp = Array(n + 1).fill().map(() => Array(n + 1).fill(0));
  const m = Array(n + 1).fill().map(() => Array(n + 1).fill(0));

  for (let l = 2; l <= n; l++) {
    for (let i = 1; i <= n - l + 1; i++) {
      const j = i + l - 1;
      dp[i][j] = Infinity;
      for (let k = m[i][j-1]; k <= m[i+1][j]; k++) {
        const cost = dp[i][k] + dp[k+1][j] + p[i-1] * p[k] * p[j];
        if (cost < dp[i][j]) {
          dp[i][j] = cost;
          m[i][j] = k;
        }
      }
    }
  }

  return dp[1][n];
}

function maxSlidingWindow(nums, k) {
    const dq = [];
    const result = [];

    for (let i = 0; i < nums.length; i++) {
        // Remove indices that are out of the current window
        while (dq.length > 0 && dq[0] <= i - k) {
            dq.shift();
        }

        // Remove indices whose values are less than current element
        while (dq.length > 0 && nums[dq[dq.length - 1]] < nums[i]) {
            dq.pop();
        }

        dq.push(i);

        // Add the maximum to result once window is formed
        if (i >= k - 1) {
            result.push(nums[dq[0]]);
        }
    }

    return result;
}

// Example usage:
const nums = [1, 3, -1, -3, 5, 3, 6, 7];
const k = 3;
console.log(maxSlidingWindow(nums, k)); // [3, 3, 5, 5, 6, 7]

def min_insertions_slope_trick(s):
    # Initialize the slope function with zero cost
    slope_func = []
    cost = 0

    for char in s:
        if char == '(':
            # Add a new segment with slope 1
            slope_func.append((0, 1))
        else:
            # Add a new segment with slope -1
            slope_func.append((0, -1))
            # Merge segments to maintain piecewise linearity
            cost += merge_segments(slope_func)

    return cost

def merge_segments(segments):
    # Simplified logic for demonstration
    # In practice, this involves merging overlapping segments and updating costs
    return 0

# Example usage:
# print(min_insertions_slope_trick("(()))"))

function coinChange(coins, amount) {
    const dp = new Array(amount + 1).fill(Infinity);
    dp[0] = 0;

    for (let i = 1; i <= amount; i++) {
        for (const coin of coins) {
            if (coin <= i && dp[i - coin] !== Infinity) {
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
    }

    return dp[amount] === Infinity ? -1 : dp[amount];
}

function climbStairs(n) {
    if (n <= 2) return n;
    let prev2 = 1;
    let prev1 = 2;
    for (let i = 3; i <= n; i++) {
        let current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }
    return prev1;
}

const tasks = [
  { id: 'task1', duration: 2, resources: 3 },
  { id: 'task2', duration: 1, resources: 2 },
  { id: 'task3', duration: 3, resources: 1 }
];

const maxResources = 5;
const dp = new Map();

// Initialize base case
dp.set('0_0', 0); // time 0, resources used 0

// For each task, update states
for (let i = 0; i < tasks.length; i++) {
  const task = tasks[i];
  const newStates = new Map();

  for (const [state, value] of dp.entries()) {
    const [time, resources] = state.split('_').map(Number);
    
    // If task can be scheduled
    if (resources + task.resources <= maxResources) {
      const newTime = time + task.duration;
      const newResources = resources + task.resources;
      const newState = `${newTime}_${newResources}`;
      
      if (!newStates.has(newState) || newStates.get(newState) < value + 1) {
        newStates.set(newState, value + 1);
      }
    }
  }

  // Merge new states into dp
  for (const [state, value] of newStates.entries()) {
    dp.set(state, value);
  }
}

console.log(dp); // Shows all valid states and their optimal values

const arr = [5, 3, 8, 2];
let sos = new Array(arr.length);
sos[0] = arr[0]; // 5
for (let i = 1; i < arr.length; i++) {
    sos[i] = sos[i - 1] + arr[i];
}
console.log(sos); // [5, 8, 16, 18]

function countNumbersWithDigitSum(n, k) {
    const memo = new Map();
    
    function dp(pos, sum, tight, started) {
        if (pos === n.length) {
            return sum === k ? 1 : 0;
        }
        
        const key = `${pos}-${sum}-${tight}-${started}`;
        if (memo.has(key)) return memo.get(key);
        
        let limit = tight ? parseInt(n[pos]) : 9;
        let result = 0;
        
        for (let digit = 0; digit <= limit; digit++) {
            if (!started && digit === 0) {
                result += dp(pos + 1, sum, tight && (digit === limit), false);
            } else {
                result += dp(pos + 1, sum + digit, tight && (digit === limit), true);
            }
        }
        
        memo.set(key, result);
        return result;
    }
    
    return dp(0, 0, true, false);
}

// Example usage:
console.log(countNumbersWithDigitSum("123", 6)); // Count numbers from 0 to 123 with digit sum = 6