Computer scienceProgramming languagesJavaInterview preparationAlgorithms and problem solving techniques

Dynamic programming approach in action

Treasure hunting

Report a typo

Imagine that we have a grid of M x N cells, each of which has a pile of gold. Write a program that finds the maximum amount of gold that can be collected along the path between the top left corner and the bottom right corner of the grid, provided that you can move only to the right or to the bottom of each cell:

a grid of M x N cells

The input of the program must be following:

First line is the number of rows N (3 ≤ N ≤ 10), the second line is the number of cells M (3 ≤ M ≤ 10) in each row and then N lines of M positive integers in each separated by blank spaces, representing the amount of gold in each cell.

Sample Input 1:

3
5
65 48 92 95 34
92 83 65 19 40
14 98 88 27 52

Sample Output 1:

Sample Input 2:

7
5
55 37 55 57 25
28 29 14 34 81
70 60 73 48 86
50 38 26 11 46
96 78 57 74 35
85 51 20 51 88
98 53 76 23 72

Sample Output 2:

Write a program in Java 17

import java.util.Scanner;

class Main {

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);

// Write your code here

int maxAmount = 0;

System.out.println(maxAmount);

}

___

Create a free account to access the full topic