Problem $4(2+4+5+3=14)$ Project management

You are a high$-$level manager in a software firm and you are managing $n$ software projects. You are asked

to assign $m$ of the programmers in your firm among these $n$ projects. Assume that all of the programmers

are equally competent.

After some careful thought, you have figured out how much benefit i programmers will bring to project $j.$

View this benefit as a number. Formally put, for each project $j,$ you have computed an array $A_j[0..m]$ where

$A_j[i]$ is the benefit obtained by assigning i programmers to project $j.$ Assume that $A_j[i]$ is nondecreasing

with increasing $i.$

In this question, you will design a dynamic programming algorithm to determine how many programmers

you will assign to each project so that the total benefit obtained over all projects is maximized.

$($a$)$ Describe the set of subproblems that your dynamic programming algorithm will consider. Your solution

should look something like "For every $...,$ we define OPT$[dots]$ to be $..."$

$($b$)$ Give a recurrence expressing the solution to each subproblem in terms of the solution to smaller

subproblems.

$($c$)$ Using your recurrence, design a dynamic programming algorithm to output the optimal allocation of

programmers to the $n$ projects. You may use either a top$-$down or bottom$-$up approach. Remember

that your algorithm needs to output the optimal allocation, not only its benefit. The output of your

algorithm can be an array of length $n$ where the $i$ th entry gives the number of programmers allocated

to project $i$ in the optimal allocation.

$($d$)$ Analyze the running time and space usage of your algorithm.

I need help with part C of this. From what I know, the recurrence should be; OPT$($i$,$ j$)=$ max$($from k i$)\{$Aj$[$k$]+$ OPT$($i$-$k$,$j$-1)\}.$