Guess Number Higher or Lower II LeetCode solution in JavaScript

1
/** https://leetcode.com/problems/guess-number-higher-or-lower-ii/
2
 * @param {number} n
3
 * @return {number}
4
 */
5
var getMoneyAmount = function (n) {
6
  // Memo
7
  this.memo = new Map();
8

9
  return dp(n, 0, n);
10
};
11

12
var dp = function (n, start, end) {
13
  let key = `${start}_${end}`;
14

15
  // Base, there is only 1 node on this side of the leg, which mean our guess is always correct and it cost nothing so return 0
16
  if (end - start < 2) {
17
    return 0;
18
  }
19

20
  // Base, there are only 2 nodes on this side of the leg, which mean we only need to pick cheapest guess
21
  if (end - start === 2) {
22
    // The `start` will always be smaller so pick `start`, add 1 to account for 0 index
23
    return start + 1;
24
  }
25

26
  // Return from memo
27
  if (this.memo.has(key) === true) {
28
    return this.memo.get(key);
29
  }
30

31
  // Minimum cost
32
  let minCost = Infinity;
33

34
  // Try to arrange the tree's left and right leg and find the cost of each leg
35
  for (let i = start; i < end; i++) {
36
    let left = dp(n, start, i);
37
    let right = dp(n, i + 1, end);
38

39
    // Cost of current guess, add 1 to account for 0 index
40
    let curr = i + 1;
41

42
    // Update cost of current guess, which is the max of left or right leg
43
    curr = Math.max(left + curr, right + curr);
44

45
    // Then update the minimum cost for entire tree
46
    minCost = Math.min(minCost, curr);
47
  }
48

49
  // Set memo
50
  this.memo.set(key, minCost);
51

52
  return minCost;
53
};