LeetCode: Maximum Score From Performing Multiplication Operations Solution

1function recursion(l, i, nums, muls, memo) {
2  if (i === muls.length) {
3    return 0
4  }
5  if (memo[l][i] != null) {
6    return memo[l][i]
7  }
8
9  let left = l
10  let right = nums.length - (i - l) - 1
11  let case1 = muls[i] * nums[left] + recursion(l + 1, i + 1, nums, muls, memo)
12  let case2 = muls[i] * nums[right] + recursion(l, i + 1, nums, muls, memo)
13  memo[l][i] = Math.max(case1, case2)
14
15  return memo[l][i]
16}
17
18/**
19 * @param {number[]} nums
20 * @param {number[]} multipliers
21 * @return {number}
22 */
23var maximumScore = function (nums, multipliers) {
24  let memo = Array.from({ length: multipliers.length }, _ =>
25    Array(multipliers.length).fill(null)
26  )
27  return recursion(0, 0, nums, multipliers, memo)
28}