Dynamic Programming: Can someone please explain what is happening in this code VERBALLY?

14. You just started a consulting business where you collect a fee for completing various types of projects (the fee is different for each project). You can select in advance the projects you will work on during some finite time period. You work on only one project at a time and once you start a project it must be completed to receive your fee. There is a set of n projects P1, P2, .. Pn each with a duration di, d2, .. d, (in days) and you receive the fee f1, f2, .., fn (in dollars) associated with it. That is project p; takes d days and you collect f dollars after it is completed. Each of the n projects must be completed in the next D days or you lose its contract. Unfortunately, you do not have enough time to complete all the projects. Your goal is to select a subset Sof the projects to complete that will maximize the total fees you earn in D days. (a) What type of algorithm would you use to solve this problem? Divide and Conquer, Greedy or Dynamic Programming. Why? It is similar to the 0-1 knapsack. (b) Describe the algorithm verbally. If you select a DP algorithm give the formula used to fill the table or array. Let OPT(i,d) be the maximum fee collected for considering projects 1,..., i with d days available. The base cases are OPT(1, 0) = 0 for i = 1, ..., n and OPT(0, d) = 0 for d = 1, ..., D. For i = 1 to n { For j = 1 to D{ //updated from d to j If (di > j) { OPT(i , j) = OPT( i-1, j) // not enough time to complete project i} Else { OPT(i, j) = max ( OPT(1-1, j), // Don't complete project i OPT( 1-1, j-di) + fi ) // Complete project I and earn fee fi ) } } } (c) What is the running time of your algorithm? O(nD) or (nD)