Problem Involving Grids - 4
Explore dynamic programming strategies to solve a grid problem where two individuals start at opposite corners and meet only once to maximize their combined calories burnt. Understand how to build and use multiple DP tables that track different journey segments and compute optimal meeting points for this optimization puzzle.
We'll cover the following...
Problem statement
Let’s discuss one more complex problem based on grids. It is another variant of the grid problems that we discussed earlier. The problem statement is given below.
You are given a 2-D matrix A of n rows and m columns where A[i][j] denotes the calories burnt. Two persons, a boy and a girl start from two corners of this matrix. The boy starts from the cell (1, 1) and needs to reach the cell (n, m). On the other hand, the girl starts from the cell (n, 1) and needs to reach (1, m). The boy can move right and down. The girl can move right and up. As they visit a cell, the amount in the cell A[i][j] is added to their total of calories burnt. You have to maximize the sum of total calories burnt by both of them under the condition that they shall meet only in one cell and the cost of this cell shall not be included in either of their totals.