Function dfs

javascript/0312-burst-balloons.js:42–66

(nums, left, right, memo, result = 0)

        ); /* Time O(N) | Space O(N) */

var dfs = (nums, left, right, memo, result = 0) => {
    for (let i = left; i <= right; i++) {
        /* Time O(N) */
        const gain = nums[left - 1] * nums[i] * nums[right + 1];
        const _left = search(
            nums,
            left,
            i - 1,
            memo,
        ); /* Time O(N * N) | Space O(HEIGHT) */
        const _right = search(
            nums,
            i + 1,
            right,
            memo,
        ); /* Time O(N * N) | Space O(HEIGHT) */
        const remaining = _left + _right;

        result = Math.max(result, remaining + gain);
    }

    memo[left][right] =
        result; /*                               | Space O(N * N) */
    return result;
};

/**
 * DP - Bottom Up