Answer:
Explanation:
(a) The recurrence relation for the given problem is :
T(n) = T(n-1) + T(n-4) + 1
(b) The O(n) time recursive algorithm with memoization for the above recurrence is given below :
Create a 1-d array 'memo' of size, n (1-based indexing) and initialize its elements with -1.
func : a recursive function that accepts the cost array and startingJobNo and returns the minimum cost for doing the jobs from startingJobNo to n.
Algorithm :
func(costArr[], startingJobNo){
if(startingJobNo>n)
then return 0
END if
if(memo[startingJobNo] != -1)
then return memo[startingJobNo];
END if
int ans1 = func(costArr, startingJobNo+1) + costArr[startingJobNo]
int ans2 = func(costArr, startingJobNo+4) + h
memo[startingJobNo] = min(ans1,ans2);
return memo[startingJobNo];
}
(c)
First, Create a 1-d array 'dp' of size, N+1.
dp[0] = 0
bottomUp(int c[]){
for i=1 till i = n
DO
dp[i] = min(dp[i-1] + c[i], dp[max(0,i-4)] + h);
END FOR
return dp[n];
}
(d)
Modifying the algorithm given in part (b) as follows to know which job to do yourself and in which jobs we need to hire a handyman.
First, Create a 1-d array 'memo' of size, n (1-based indexing) and initialize its elements with -1.
Next, Create another 1-d array 'worker' of size,n (1-based indexing) and initialize its elements with character 'y' representing yourself.
Algorithm :
func(costArr[], startingJobNo){
if(startingJobNo>n)
then return 0
END if
if(memo[startingJobNo] != -1)
then return memo[startingJobNo];
END if
int ans1 = func(costArr, startingJobNo+1) + costArr[startingJobNo]
int ans2 = func(costArr, startingJobNo+4) + h
if(ans2 < ans1)
THEN
for (i = startingJobNo; i<startingJobNo+4 and i<=n; i++)
DO
// mark worker[i] with 'h' representing that we need to hire a mechanic for that job
worker[i] = 'h';
END for
END if
memo[startingJobNo] = min(ans1,ans2);
return memo[startingJobNo];
}
//the worker array will contain 'y' or 'h' representing whether the ith job is to be done 'yourself' or by 'hired man' respectively.
