Given an **m x n** matrix filled with **non-negative** integers, use dynamic programming techniques to find the maximum sum along a path from the top-left of the grid to the bottom-right. Return this maximum sum. The direction of movement is limited to right and down.

**Example:**

**Note:**

You may have previously solved the DFS variant of this problem. That won't work for large sized matrices - just consider the size of the recursion tree for a 100x100 matrix! Dynamic Programming should afford a better solution.

Input Matrix :

2 31

4 5 6

7 89

Output : 1 + 4 + 7 + 8 + 9 = 29

You may have previously solved the DFS variant of this problem. That won't work for large sized matrices - just consider the size of the recursion tree for a 100x100 matrix! Dynamic Programming should afford a better solution.

Need a **hand?** Try out these hints, one at a time.

Consider the following constraints :

1) The direction of movement is limited to down and right

2) The Matrix contains non-negative integers

We can conclude that each step in the path can be found by looking at the previous steps and picking the step that results in a maximal value. Also, since the direction of movement is heavily constrained, this problem has an**Optimal Substructure**. Create an m x n matrix that will keep the record of the maximum sum obtained at each cell in the grid. Fill the first row and column of this matrix and use this information to traverse the cells and fill each cell.

1) The direction of movement is limited to down and right

2) The Matrix contains non-negative integers

We can conclude that each step in the path can be found by looking at the previous steps and picking the step that results in a maximal value. Also, since the direction of movement is heavily constrained, this problem has an

1) Create a memo grid that will be used to build the solution -

2) Fill the first Row and Columns of the memo matrix :

3) Traverse over

4) Return the value stored in the last cell :

`int[][] memo = new int[m][n];`

2) Fill the first Row and Columns of the memo matrix :

for(int i = 1; i < m; i++){

memo[i][0] = memo[i-1][0] + grid[i][0];

}

for(int j = 1; j < n; j++){

memo[0][j] = memo[0][j-1] + grid[0][j];

}

3) Traverse over

`memo`

and use the information of the cells in the previous row / col to fill the current cell : for(int i = 1; i < m; i++){

for(int j = 1; j < n; j++){

memo[i][j] = grid[i][j] + Math.max(memo[i-1][j], memo[i][j-1]);

}

}

4) Return the value stored in the last cell :

`return memo[m-1][n-1];`

public static int matrixMaxSumDP(int[][] grid) { }

**C**

**Java**

**Python**