Consider the minimum perfect squares problem. Given a posit…
Consider the minimum perfect squares problem. Given a positive integer, we want to find the least number of squares of integers that we need to sum to get that number. For example, if I give you the number 5, then this can be written as a sum of squares in two different ways: or . So, the minimum number of terms you need is 2. As another example, consider 11. This can be written as a sum of squares in many ways, but the one with the fewest terms is . So, the minimum number of terms required is 3. Your problem is to write pseudocode that will compute the answer to the minimum perfect squares problem using dynamic programming. To be specific, here are some inputs and outputs: Input: 2. Output: 2 () Input: 5. Output: 2 () Input: 11. Output: 3 () Input: 99. Output: 3 () Your code should only output the number of terms in the sum. Do not output which squares are in the sum. (So, for example, if you input 11, your function should just return the number 3.) Hint: Let be the minimum number of perfect squares needed for . Then, notice that you can break this into subproblems via
Read Details