Medium Divide and Conquer > Dynamic Programming

In this problem, you will be given a 2D matrix with **N** rows and **M** columns. There is a Pacman in the (1,1) position. He can move only to right or only to down. Each cell of the matrix contains some coin values. If Pacman moves to a cell then he earns that amount of coin value that the cell contains. Your task is to calculate the maximum number of coins the Pacman can earn if he wants to reach to the cell (N,M). Input: ------ First line of input contains an integer **T** that denotes the number of test cases **(T<=100)**. Next line contains two integers **N** and **M** separated by space **(1 <= N,M <=100)**. Next N lines contains M integers separated by space which denotes the coin value of that cell. **(coin value <=1000)** Output: ------- For each set of inputs, print a single integer in a single line, the maximum coin values that Pacman can earn Sample Input ------------ 2 5 6 1 6 2 3 4 5 9 1 2 1 8 6 2 5 8 6 10 5 8 5 9 4 2 8 23 5 8 5 9 6 2 3 1 5 3 4 2 6 Sample Output ------------- 76 15

Md. Samiul Alam