3. The Longest Increasing Subsequence (6 pts) The Longest Increasing Subsequence (LIS) problem is to find the length of the longest subsequence of a given sequence such that all elements of the subse- quence are sorted in increasing order. For example, the length of LIS for 10, 22, 9, 33, 21, 50, 41, 60, 80 is 6 and LIS is 10, 22, 33, 50, 60, 80 1) Define the state, decisions, transition function, and cost function of dynamic programming approach for this problem. Write out the Bellman equation for this problem (4 pts) 2) Design your DP solution for this problem (briefly explain your algorithm and then write down your pseudocode). (2 pts)