What can be the optimized algorithm to solve this problem ?
Given a matrix with M rows and N columns (M x N). In each cell there’s a number of apples.
You start from the upper-left corner of the matrix. You can go down or right one cell. You need to arrive to the bottom-right corner. Then you need to go back to the upper-left cell by going each step one cell left or up. Find the maximum number of apples you can collect.When you pass through a cell - you collect all the apples left there.
Restrictions: 1 < N, M <= 50 ; each cell contains between 0 and 1000 apples inclusive