Let M be a n m integer matrix (with n rows and m columns). Assume that rows are numbered 0, 1, 2, , n1 and columns are numbered 0, 1, 2, m1. Let M[i, j] refers to the cell in ith row and jth column. A vertical cut V of M is a sequence of 2n integers [x0, y0, x1, y1, , xn1, yn1] such that the following holds

1. x0 = 0, y0 {0, , m 1}

2. For 1 i

3. For 1 i

The cost of a vertical cut V = [x0, y0, x1, y1, , xn, yn] is defined as

Cost(V ) = M[x0, y0] + M[x1, y1] + + M[xn1, yn1]

Given a matrix, the min-cost vertical cut, denoted M inV C(M), is a vertical cut whose cost is the smallest.

Your goal is to find a path/cut from a cell in top row to a cell in the last row such that the cost of the cut is minimized over all possible way of going from a cell in top to a cell in bottom.

Write the following method using Java

minCostVC(int[][] M): Returns a min-cost vertical cut. Type of this method must be array list of integers. Note that if M has n rows, the the returned array list has exactly 2n integers. You must use dynamic programming paradigm to arrive at your code. For this, first define the recurrence relation. Then arrive at an iterative solution. Your code must be iterative, not recursive and should not use use memoization

\ 3 1513 32-3 28-5 14-1