Dynamic Programming Let G = (V, E) be a line graph such that V = {v1, v2, · · · , vn} and for every i, 1 ≤ i < n − 1, there is an edge ∈ E from vi to vi+1. Each vertex v has a non-negative weight w(v). A set S ⊆ V is an Independent Set if for every x, y ∈ S, there is no edge from x to y in G. The weight of an independent set S is X v∈S w(v) Give a dynamic programming based algorithm to compute a maximum weight independent set. Your solution must give the recurrence relation that captures the weight of maximum weight independent set and describe an iterative algorithm based on the recurrence relation. No credit is given if your solution does not describe the recurrence relation or uses a recursive algorithm. Part of the grade depends on efficiency.