TopCoder problem "RGBStreet" used in SRM 325 (Division II Level Two)



Problem Statement

    

The people of RGB Street have decided to paint each of their houses red, green, or blue. They've also decided that no two neighboring houses will be painted the same color. The neighbors of house i are houses i-1 and i+1. The first and last houses are not neighbors.

You will be given a String[] houses, where the ith element corresponds to house i. Each element of houses will be formatted as "R G B" (quotes for clarity only), where R, G and B are the costs of painting the corresponding house red, green, and blue, respectively. Return the minimal total cost required to perform the work.

 

Definition

    
Class:RGBStreet
Method:estimateCost
Parameters:String[]
Returns:int
Method signature:int estimateCost(String[] houses)
(be sure your method is public)
    
 

Constraints

-houses will contain between 1 and 20 elements, inclusive.
-Each element of houses will be in the format "R G B" (quotes for clarity only), where R, G and B are integers with no leading zeroes.
-In each element of houses, the values R, G and B will be between 1 and 1000, inclusive.
 

Examples

0)
    
{"1 100 100", "100 1 100", "100 100 1"}
Returns: 3
"RGB" is the best choice, and the total cost of the work is equal to 3.
1)
    
{"1 100 100", "100 100 100", "1 100 100"}
Returns: 102
The minimum possible cost is 102, and there are two solutions that result in that cost: "RGR" and "RBR".
2)
    
{"26 40 83", "49 60 57", "13 89 99"}
Returns: 96
3)
    
{"30 19 5", "64 77 64", "15 19 97", "4 71 57", "90 86 84", "93 32 91"}
Returns: 208
4)
    
{"71 39 44", "32 83 55", "51 37 63", "89 29 100", 
 "83 58 11", "65 13 15", "47 25 29", "60 66 19"}
Returns: 253

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10005&pm=6680

Writer:

Andrew_Lazarev

Testers:

PabloGilberto , brett1479 , Yarin , Olexiy

Problem categories:

Dynamic Programming