4. Scooby-Doo is stuck in an n x n sized haunted room. Each 1x1 square in this room has a certain amount of Scooby Snacks. The top left corner of the room is (1,1). You are given the function: MAX-SCOOB-SNACK(H) where H is an n x n table representing the room that Scooby is in. H[i][j] contains the number of Scooby Snacks in the square that is in the ith row and jth column of the room. Scooby needs to maximize the number of Scooby Snacks he eats to escape. If he is at (i, j), he can only go to (i +1,j), (i +1, j+1) or (i+1, j - 1) square from his current location. (i.e., He can only move directly south, southwest or southeast.) If he violates these rules, a monster will eat him! Scooby escapes when there are no more possible moves from his position. Assume that Scooby can start at any square in the top row. MAX-SCOOB-SNACK(H1..n][1..n]) should return the maximum number of Scooby Snacks that Scooby can eat before his escape, given the aforementioned constraints. Help me escape! 1.- ---/ ------ (.'----- -----) | INII)-----II RI ILIR) (a) Write, with justification, base case(s) and a recurrence relation for computing MAX- SCOOB-SNACK(H). Hint: The recurrence relation can be for a helper function. (b) Write pseudocode for a "bottom-up dynamic programming algorithm that uses tabu- lation to solve MAX-SCOOB-SNACK. 4. Scooby-Doo is stuck in an n x n sized haunted room. Each 1x1 square in this room has a certain amount of Scooby Snacks. The top left corner of the room is (1,1). You are given the function: MAX-SCOOB-SNACK(H) where H is an n x n table representing the room that Scooby is in. H[i][j] contains the number of Scooby Snacks in the square that is in the ith row and jth column of the room. Scooby needs to maximize the number of Scooby Snacks he eats to escape. If he is at (i, j), he can only go to (i +1,j), (i +1, j+1) or (i+1, j - 1) square from his current location. (i.e., He can only move directly south, southwest or southeast.) If he violates these rules, a monster will eat him! Scooby escapes when there are no more possible moves from his position. Assume that Scooby can start at any square in the top row. MAX-SCOOB-SNACK(H1..n][1..n]) should return the maximum number of Scooby Snacks that Scooby can eat before his escape, given the aforementioned constraints. Help me escape! 1.- ---/ ------ (.'----- -----) | INII)-----II RI ILIR) (a) Write, with justification, base case(s) and a recurrence relation for computing MAX- SCOOB-SNACK(H). Hint: The recurrence relation can be for a helper function. (b) Write pseudocode for a "bottom-up dynamic programming algorithm that uses tabu- lation to solve MAX-SCOOB-SNACK