Implement the solution to the Maximum Weight Independent Set in a Path Graph with Non-Negative Weights problem using dynamic programming.?

The Maximum Weight Independent Set in a Path Graph problem is defined as follows: given a path graph G = (V, E) with non-negative weights w1, w2, ..., wn on its n vertices, find a set S of non-adjacent vertices such that the sum of their weights is maximum.

The dynamic programming approach to this problem involves computing the maximum weight independent set up to each vertex i in the graph. By doing so, we can derive the maximum weight independent set of the entire graph by considering the two cases: either vertex n is in the set or it is not.

Let MISi be the maximum weight independent set up to vertex i. We can compute MISi using the following recurrence:

MISi = max(MISi-1, MISi-2 + wi)

where MISi-1 represents the maximum weight independent set that excludes vertex i, and MISi-2 + wi represents the maximum weight independent set that includes vertex i.

To compute the maximum weight independent set of the entire graph, we simply consider the two cases:

1. If vertex n is in the set, then the maximum weight independent set is MISn.

2. If vertex n is not in the set, then the maximum weight independent set is MISn-1.

Therefore, the solution to the problem is max(MISn, MISn-1).

Here is the Java code that implements this dynamic programming approach:

public static int maxWeightIndependentSet(int[] weights) {
    int n = weights.length;
    int[] mis = new int[n];
    mis[0] = weights[0];
    mis[1] = Math.max(weights[0], weights[1]);

    for (int i = 2; i < n; i++) {
        mis[i] = Math.max(mis[i-1], mis[i-2] + weights[i]);
    }

    return mis[n-1];
}

In this code, ‘weights‘ is an array of non-negative weights on the vertices of the path graph. The ‘mis‘ array stores the maximum weight independent set up to each vertex i in the graph. The ‘maxWeightIndependentSet‘ function returns the maximum weight independent set of the entire graph by computing the maximum of MISn and MISn-1. The time complexity of this algorithm is O(n), where n is the number of vertices in the path graph.