TopCoder problem "MoneyRun" used in TCCC '04 Qual. 5 (Division I Level Two)

Problem Statement

*** You may only submit a given problem once - no resubmissions will be accepted. ***

You have been given the opportunity of a lifetime. You and your friend get to run through a field full of money. Everything you and your friend pick up, you can keep. You will be given a String[] grid containing the locations of the prizes. Each character in grid will be a digit from 0-9 determining how much money is located in that particular location. The elements of grid will be the rows of the field. You and your friend will begin at row 0 column 0 of grid (element 0 character 0). Using only steps to the right and steps down, return the maximum amount of money both of you can collect. Here 'right' means increasing column value and 'down' means increasing row value. Note that you and your friend can take different routes. If you and your friend visit the same location, only one of you can pick up the money at that location. Both you and your friend will always end up on the lower rightmost location when you finish.

Definition

Class:	MoneyRun
Method:	getMost
Parameters:	String[]
Returns:	int
Method signature:	int getMost(String[] grid)
(be sure your method is public)

Constraints

grid will contain between 2 and 7 elements inclusive.

Each element of grid will contain between 2 and 7 characters inclusive.

Each element of grid will contain the same number of characters.

Each character in grid will be a digit ('0'-'9').

Examples

{
"111",
"101",
"111"}

Returns: 8

Let Y denote where you will pick up money, and H denote where he will. A possible solution is

	YYY
        H0Y
        HHH ,

since you are able to pick up all 8.

{
"99",
"09"
}

Returns: 27

Any way you try this, you can't get more than 27.

{
"09933",
"29333",
"03333",
"41111"}

Returns: 52

{"11111",
 "22222"}

Returns: 15

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=2324

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=5004&pm=2324

Writer:

brett1479

Testers:

lbackstrom , schveiguy

Problem categories:

Brute Force, Dynamic Programming, Recursion, Search