Best Sum with Tabulation

Updated: 01 February 2024

Problem

The same problem as the Memoization Best problem but we want to take a tabular approach which we can do as an adaptation of the Tabular Can How Sum problem but this time we replace each sub-sum with the shortest sum of the given options

Tabulation Implementation

The implementation of this can be seen below:

1
export const bestSum = (target: number, nums: number[]): number[] | null => {
2
  const table = new Array<number[] | null>(target + 1).fill(null);
3
  table[0] = [];
4

5
  for (let index = 0; index <= target; index++) {
6
    const element = table[index];
7

8
    if (element) {
9
      for (const num of nums) {
10
        const nextIndex = index + num;
11
        if (nextIndex in table) {
12
          const nextValue = [...element, num];
13

14
          const currentValue = table[nextIndex];
15

16
          if (currentValue === null || currentValue.length > nextValue.length)
17
            table[nextIndex] = nextValue;
18
        }
19
      }
20
    }
21
  }
22

23
  return table[target];
24
};

In the above, the time complexity $O(m^2 *n)$ and space complexity $O(m^2)$

The reason we say $m^2$ and not $m$ in the time complexity is because of the array copy operation that we do to assign the latest value