Q$1)$ Show the trace of the dynamic programming$-$based LCS algorithm on sequences

A $=$dbbcd$,$ B $=$bcd$$ and $$backtracking steps.

$$

$$

$$

$$

Q$2)$ In the following problem we are trying to find the number of times a pattern occurs as a $($possibly non$-$contiguous$)$ subsequence of a string. For example, if the pattern we are looking for is mom and the string is moneymcom then the number of occurrences is $4.$

$$

moneymcom

moneymcom

moneymcom

moneymcom

$$

$$

Give a dynamic programming algorithm to solve this problem. Explain the subproblems you are building your optimal solution from, give a recurrence relation and execute your algorithm on an example string.

$$

$$

$$

$$

Q$3)$For each day, you can choose to go to gym or stay in and have rest. If you go to gym, you will increase your fitness score. But you can only go to gym for two consecutive days $$ if you go to a gym three days in a row, you$$ll be too tired and can$$t go to school the next day. You know how much fitness score you will gain by going go gym that dat and you also know you get $0$ fitness from staying in$.$ These values are stored in input array F$.$ Your goal is to maximize the sum of the fitness scores for the days you go to gym, while not going for more than two consecutive days. For instance maximum fitness score of $[3,3,1,3,3]$ is $12$ where we should go to gym on days $1,2$ and $4,5.$

$$

Provide a dynamic programming solution to this problem.Explain the subproblems you are building your optimal solution from, give a recurrence relation. Execute the algorithm with another example input than provided above.