1751-maximum-number-of-events-that-can-be-attended-ii.js

/**
 * @param {number[][]} events
 * @param {number} k
 * @return {number}
 */
const maxValue = function (events, k) {
  const n = events.length
  const memo = Array.from({ length: n + 1 }, () => Array(k + 1).fill(-1))
  events.sort((a, b) => a[0] === b[0] ? a[1] - b[1] : a[0] - b[0])
  return helper(memo, events, n, 0, k)
}

function helper(memo, events, n, i, k) {
  if(i === n || k === 0) return 0
  if(memo[i][k] !== -1) return memo[i][k]
  let ni = i + 1
  for(; ni < n; ni++) {
    if(events[ni][0] > events[i][1]) break
  }

  return memo[i][k] = Math.max(
    helper(memo, events, n, i + 1, k),
    events[i][2] + helper(memo, events, n, ni, k - 1)
  )
}

// another

/**
 * @param {number[][]} events
 * @param {number} k
 * @return {number}
 */
const maxValue = function (events, k) {
  // d[i][j] 表示以 events[i]结尾的取最多j个最大值
  // d[i][j-1],  Math.max( d[m][j-1] + v[i]) for m ending < start[i]
  events.sort((a, b) => a[1] - b[1])
  const n = events.length
  let d = []
  for (let j = 0; j <= k; j++) {
    const newD = []
    for (let i = 0; i < n; i++) {
      if (j === 0) {
        newD[i] = 0
      } else if (j === 1) {
        newD[i] = events[i][2]
      } else if (i === 0) {
        newD[i] = events[i][2]
      } else {
        newD[i] = d[i] // 以i结尾最多取j-1次的最大值
        const v = events[i][2]
        const start = events[i][0]
        for (let m = 0; m < i; m++) {
          if (events[m][1] < start) {
            if (d[m] + v > newD[i]) {
              newD[i] = d[m] + v
            }
          } else {
            break
          }
        }
      }
    }
    d = [...newD]
  }
  return Math.max(...d)
}


// another


/**
 * @param {number[][]} events
 * @param {number} k
 * @return {number}
 */
const maxValue = function(events, k) {

        cache = new Map();
        events.sort((a,b) => a[0] - b[0]);
        return dfs(events, 0, -1, k);
    
    function dfs(events, idx, end, k){
        let key = idx + "," + end + "," + k;
        if(cache.has(key)){
            return cache.get(key);
        }
        if(idx >= events.length){
            return 0;
        }
        if(k == 0) {
            return 0;
        }
        let max = 0;
        if(events[idx][0] > end){
            max = Math.max(max, dfs(events, idx+1, events[idx][1], k-1) + events[idx][2]);
        }
        
        max = Math.max(max, dfs(events, idx+1, end, k));
        cache.set(key, max);
        return max;
    }
};