Dynamic Programming

• Tutorial-1, Tutorial-2

Part-1: Memoization

Part-2: Tabulation

• canSum -> Decision Problem
• howSum -> Combinaroeic Problem
• bestSum -> Optimization Problem

ChatGPT question

Request:
I have a dynamic programming problem and its solution. I need an explanation of how tabulation is used in the code. Please provide the explanation as comments within the code, and also include a detailed analysis of the time and space complexity. Here is the problem and the code:

Problem:
Write a function bestSum(targetSum, numbers) that takes in a targetSum and an array of numbers. The function should return an array containing the shortest combination of numbers that add up to exactly the targetSum. If there is a tie for the shortest combination, you may return any one of the shortest.

Code:

```
```

Additional Note:
Please provide a detailed explanation of the time and space complexity for this solution as well.
Please provide a detailed explanation about how tabulation has been implemented in this program.