Minimum Cost to Split an Array - DP - Top Down & Bottom Up [JS]

Description 

Solution 1: DP - Recursion w/ Memoization

Memoize each dp(i), where dp(i) = the minimum cost to split the subarray from index i to the end of nums.
For each dp(i),

• Go through every possible index j from i to n - 1. Try to take the subarray of range [i, j].
• To calculate the number of length of the trimmed subarray:
  Count the number of unique numbers. Get the trimmed length by: length of subarray - number of unique numbers.
  Keep track of the count of each number in a hashmap.
  If the current count is 0, add to the uniqueCount (it is the first time we see this number, so it is unique)
  If the current count is 1, subtract from uniqueCount (was previously a unique number)

Time Complexity: O(n^2)
Space Complexity: O(n)

var minCost = function(nums, k) {
  let n = nums.length, memo = Array(n).fill(-1);
  return dp(0);
  
  function dp(i) {
    if (i === n) return 0;
    if (memo[i] !== -1) return memo[i];
    
    let ans = Infinity, count = new Map(), uniqueCount = 0;
    for (let j = i; j < n; j++) {
      let currCount = count.get(nums[j]) || 0;
      if (currCount === 0) {
        uniqueCount++;
      } else if (currCount === 1) {
        uniqueCount--;
      }
      count.set(nums[j], currCount + 1);
      let nonUnique = (j - i + 1) - uniqueCount;
      let cost = k + nonUnique;
      ans = Math.min(ans, cost + dp(j + 1));
    }
    return memo[i] = ans;
  }  
};

Solution 2: DP - Bottom Up

Same idea as solution 1, except using iteration and going bottom-up instead of top-down.

Time Complexity: O(n^2)
Space Complexity: O(n)

var minCost = function(nums, k) {
  let n = nums.length, dp = Array(n + 1).fill(Infinity);
  dp[0] = 0;
  for (let i = 0; i < n; i++) {
    let count = new Map(), uniqueCount = 0;
    for (let j = i; j >= 0; j--) {
      let currCount = count.get(nums[j]) || 0;
      if (currCount === 0) {
        uniqueCount++;
      } else if (currCount === 1) {
        uniqueCount--;
      }
      count.set(nums[j], currCount + 1);
      let nonUnique = (i - j + 1) - uniqueCount;
      let cost = k + nonUnique;
      dp[i + 1] = Math.min(dp[i + 1], cost + dp[j]);
    }
  }
  return dp[n];
};