For a grid arranged with m rows and n columns, you need to create a barrier that extends from row 1 to row m (and it wil

[answerhappygod]

For a grid arranged with m rows and n columns, you need tocreate a barrier that extends from row 1 to row m (and it willoccupy a pair of adjacent squares in each row). The goal is tomaximize the squares that are not occupied by the barrier. There isno restriction on where in row 1 the barrier starts, and it isallowed to zig-zag left and right, but it can only shift by oneseat per row. There is also no requirement about balancing thenumber of squares on each side of the barrier. For example, placingthe entire barrier in the leftmost two columns is ok.) Each square(i, j) has a positive price P (i, j), which is O(1) time. Thecomplete barrier cost is the sum of the prices of the 2m squares itoccupies.
Design a dynamic programming algorithm that computes the minimumpossible cost of a complete barrier and runs in O(mn) time