2. Give recurrence relations (including base cases) that are suitable for dynamic programming solutions to the following problems. You do not need to prove your correctness. (a) LONGEST-ARITHMETIC-SUBSEQUENCE(A, d): Given an array of integers A and a differ- ence d, return the length of the longest arithmetic subsequence in A with difference d. That is, return the longest subsequence S such that S[i + CLIMB-STAIRS(n): There are n steps to climb. Return the number of ways there are for a person standing at the bottom to reach the top if they can climb either 1 or 2 steps at a time. (c) In today's age, many people rely on search engines such as Google as their primary source to get the information they need. When we type fast, we often forget to insert es between the words we enter into search bars. However, search engines are usually still able to look for the correct information. This is in part facilitated by the ability to check and see if the input string can be split into dictionary words. You can implement a function that does this yourself using dynamic programming! WORD-BREAK(LW): You are given a string W and a list of words L. If the string can be segmented into a space separated sequence such that all of the separated words exist in the list, return true. Otherwise, return false. Note: you are allowed to reuse list words more than once. Examples: Input: L = [*EECS', '376', 'Is, Awesome'], W = Awesome EECS376Is Awesome'. Output = true Input: L = ['cats, and', 'dogs'], W = "catsanddogs'. Output = true Input: L = ['cats, and', 'dogs'], W = "catsandogs'. Output = false Input: L = ['cats', 'and', 'dogs'], W = 'catsand'. Output = true