3. (Dynamic Programming - 20 points) You are given a checkerboard with 4 rows and n columns with an integer written in each square. You are also given 2n pieces of paper, such that each piece of paper covers exactly one square. You need to place some or all of these pieces of paper on the checkerboard (at most one piece per square) so as to maximize the sum of integers covered by the pieces of paper. However, in order for your placement to be legal, no two pieces of paper can be placed on horizontally or vertically adjacent squares (diagonal adjacency is allowed). Design an efficient dynamic programming algorithm to compute the optimal value to this problem. (a) (2 points) Describe this problem formally in the Input: ..., Output: ... format. (b) (3 points) Find out the number of legal patterns of pieces of paper that can occur in any column (in isolation, ignoring the neighboring columns). Describe these patterns. (c) (2 points) Two patterns from the previous part are compatible if they can be placed on adjacent columns to form a legal placement. Give one example of compatible patterns. Give one example of non-compatible patterns. (d) (4 pts) Consider subproblems consisting of the first i columns with 1 Sisn. Each subproblem can be assigned a type which is the pattern occurring in the last column. Based on this, describe the semantic array. State what the answer to the whole problem is based on your array. (e) (4 pts) Describe the computational array. Do not forget the base case. (f) (4 pts) Describe your algorithm in pseudocode. (g) (1 pt) What is the runtime of your algorithm? Why