Treasure island

★★★★★

4.5

2 votes

Algorithms, Dynamic Programming, Medium, Two dimensional

Details

Submissions

Discussion

Editorial

Problem

Monk wants to divide an island which is in the form of N * M matrix into pieces of $1*1$ matrices.He can do the splitting of the island by making a horizontal cut or a vertical cut. In each case the island gets divided into 2 pieces. There are certain coins in each cell. The cost of split is the sum of all the cells in the island which is to be split.

Monk wants to split the island in minimum cost.Help Monk do so.

$Input Format$

First line contains 2 integers N and M.

Then N lines follow each containing M integers.

$Output Format$

Print the minimum cost required.

$Constraints$

$1 \le N,M \le 50$

$1 \le coins \le10^5$

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

First we split the matrix with cost 8 and get 2 matrices as (2,2) and (1,3).

Now we can split (2,2) with cost 4 into (2) and (2).

Now we can split (1,3) with cost 4 into (1) and (3).