Problem 4. We want to give our dog a collection of treats with total satisfaction value exactly equal to S. For that, we have a collection of n different treats in an array T[1:n] where T[i] is the satisfaction value of the i-th treat (all treats have distinct satisfaction values). Our goal is to give our dog treat satisfaction of exactly S by giving her the smallest possible number of treats or outputting that it is not possible with this collection of treats. Design a dynamic programming algorithm for this problem of outputting the number of treats we should give our dog with worst-case runtime of O(nS). (25 points) Remember to separately write your specification of recursive formula in plain English ( 7.5 points), your recursive solution for the formula and its proof of correctness ( 7.5 points), the algorithm using either memoization or bottom-up dynamic programming ( 5 points), and runtime analysis ( 5 points). Example: - Given S=15,n=7, and T=[4,9,3,2,7,5,6], the correct answer is 2 by picking T[2]=9 and T[7]=6 which add up to 15 . - Given S=11,n=4, and T=[4,3,5,9], the correct answer is that 'the satisfaction cannot be met' as no combination of these treats adds up to a value of 11 (recall that we can only use each treat once)