https://community.topcoder.com/stat?c=problem_statement&pm=1215&rd=4555
https://blog.csdn.net/makeway123/article/details/45116447
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
https://blog.csdn.net/makeway123/article/details/45116447
给一个目标字符串，每次可以在空白字符串上将连续的位置刷成某个字符，问最少刷几次变成目标字符串。
如：AAA则是一次，ABA先刷成AAA再刷成ABA需要两次；RGBGRB 需要4次。
字符串长度最多50。
* It is not hard to see the state variable can be determined by (1) the start and ending positions
* of the stripe ; (2) the color. Since we will deduce the colors from the input, a state can rely
* on just the starting and ending positions only.
*
* The key to this questions is the fact that two adjacent chars who share the same color can be
* painted in one stroke.
*
* The state transition formula is :
* Left f(i,j) be the minimum number of strokes to paint S[i..j], then we have
*
* f(i,i): obviously it requires one 1 stroke ; // a single character
* f(i,j): we will break the input into two parts, and compute their costs f(i,k) and f(k+1,j) for i<=k<j
* when combining the two costs, we need to consider the following cases:
* if S[i] == S[j] then we can save 1 stroke ==> f(i,j) = f(i,k) + f(k+1, j) -1
* if S[k] == S[k+1] then we can also save 1 stroke ==> f(i,j) = f(i,k) + f(k+1,j) -1
* we compare these two cases because they are same-color cases on the boudaries of
* two subproblems.
*
* Now the difficulty is in the programming: when calculating f(i,j), we need to make sure
* f(i+1,j) and f(i, j-1) are available. From a visual perspective, we are computing a upper
* triangluar matrix based on the input string. Initially the diagonal can be easily filled
* with values of 1.
*
* ABOUT DP:
* Usually we only use DP and the input to compute a matrix. The key is in the computation
* rather than in the manipulating the input. So don't need to worry about how to manipulate the
public int minStrokes(String stripe){
int [][]dp=new int[stripe.length()][stripe.length()];
for(int [] d : dp) Arrays.fill(d,1000);
for(int x=0; x<stripe.length(); x++) dp[x][x]=1; // basic cases
for(int size=1; size<stripe.length(); size++)
for(int from=0; from<stripe.length(); from++){
int to=from+size;
if(to>=stripe.length()) continue;
int min=50;
for(int k=from; k<to; k++){
min = Math.min(min, dp[from][k]+dp[k+1][to]);
// NOTE: now we have to subproblems S[from..x] and S[x+1..to]
// We need to consider the equlity cases for both ends of subproblems:
// i.e. S[from]==S[x], S[from]==[to], S[x] == S[x+1] and S[x+1] == S[to]
//
// The following statements only considers the equality case between the two subproblems
// i.e., (1) stripe[from] = stripe[x+1], (2) stripe[x] and stripes[x+1]
// It is unnecessary to compare the equality cases inside the two subproblems:
// i.e., (2) stripe[from] == stripe[x] and (2) stripe[x+1] and stripe[to]
// as these cases will be considered when dealing with those subproblems.
if(stripe.charAt(k)==stripe.charAt(k+1)) min=Math.min(min, dp[from][k]+dp[k+1][to]-1);
if(stripe.charAt(from)==stripe.charAt(to)) min=Math.min(min, dp[from][k]+dp[k+1][to]-1);
}
dp[from][to]=min;
}
return dp[0][stripe.length()-1];
}
/**
* Another implementation using memorisation technique
*
* @param stripe
* @return
*/
public int minStrokesM(String stripe){
int nChars = stripe.length();
int [][]dp=new int[nChars][nChars];
for(int [] d : dp) Arrays.fill(d,-1);
for(int x=0; x<stripe.length(); x++) dp[x][x]=1; // basic cases
return getValue(stripe, dp, 0, nChars-1);
}
protected int getValue(String stripe, int[][] dp, int i, int j){
if( dp[i][j] != -1 ) return dp[i][j];
int min = Integer.MAX_VALUE ;
for(int k=i; k<j; k++){
int value = getValue(stripe, dp, i, k) + getValue(stripe, dp, k+1, j);
min = Math.min(min, value );
if( stripe.charAt(i) == stripe.charAt(j))
min = Math.min(min, value-1);
if( stripe.charAt(k) == stripe.charAt(k+1))
min = Math.min(min, value-1);
}
dp[i][j] = min ;
return dp[i][j];
}
/**
* Output the Dynamic Programming's state matrix, for debugging purpose
* @param dp
*/
protected static void printStateMatrix(int[][] dp)
{
int nSize = dp.length;
PrintStream out = System.out ;
out.print(" \t");
for(int i=0; i<nSize; i++)
out.print(i +"\t");
out.println();
for(int i=0; i<nSize; i++){
out.print(i + "\t");
for(int j=0; j<nSize; j++)
out.print( dp[i][j] +"\t");
out.println();
}
out.println();
}
For any given pattern X (where X represents any number of stripes) a new pattern xX (where x is one additional stripe to the left side of X) can be created with just 1 more stroke than the number of strokes neeeded to create X. We'll use this as an upper-bound. So if the pattern X takes 10 strokes, then xX will take at most 11 - possibly less.
The strategy then is to skip the left-most stripe and solve for everything to the right of it. Then determine if the left-most stripe can be added with 0 or 1 additional strokes. For example: GR takes 2 stroke, but R GR also only needs 2 because the left-most and right-most stripes are the same color (You'd paint R first, and then put a G in the middle of it). If the ends weren't the same color, as in B GR, then a third stripe would be needed.
The loop at lines 63-67 divides the substring to the right of the current position into 2 segments. It then tries every possible combination of these segment's lengths. So, if the part to the right was 4 characters long, the first segment would be called with lengths 0, 1, 2, 3, and 4 - while the second segement would have lenghts of 4, 3, 2, 1, and 0. This ensures that each way of dividing up the part to the right is tried.
The solution also uses the notion of memoization. This has been discussed in earlier posts (see HillHike). The idea is that once a particular pattern has been calculated, we'll store it so it never needs to be calculated again. Line 70 stores each combination of start position, string length, and color that gets calculated. Then at line 48, we check to see if the combination has been calculated before. For some tests, it's not possible to finished within the time limit without this technique.
03: private static final char BLANK_COLOR = 'A' - 1;
04: private static final int MAX_COLORS = 27; // A-Z plus one for blank
05:
06: /*
07: * Holds all the combinations of starting position, string size, and color
08: * that we've encountered before. If they come up again, we can return
09: * the stored value and avoid re-calculating.
10: */
11: int[][][] alreadySeen;
12:
13: public int minStrokes(String stripes) {
14:
15: int length = stripes.length();
16:
17: /*
18: * Initialize the alreadySeen array. The Java spec guarantees all
19: * values will be set to zero. No need to do it explicitly.
20: */
21: alreadySeen = new int[length][length + 1][MAX_COLORS];
22:
23: /*
24: * Calculate calculateMinStrokes on the entire stripes String, starting
25: * with a blank canvas.
26: */
27: return calculateMinStrokes(stripes, 0, length, BLANK_COLOR);
28: }
29:
30: private int calculateMinStrokes(String stripes, int start, int size,
31: char color) {
32:
33: // Breaks the recursive calls.
34: if (size == 0) return 0;
35:
36: /*
37: * If the left-most color matches the given color, then just move
38: * on to the next stripe.
39: */
40: if (stripes.charAt(start) == color) {
41: return calculateMinStrokes(stripes, start + 1, size - 1, color);
42: }
43:
44: /*
45: * If we've already calculated this combination of starting position,
46: * string length, and colore; then just return that value.
47: */
48: if (alreadySeen[start][size][color - BLANK_COLOR] > 0) {
49: return alreadySeen[start][size][color - BLANK_COLOR];
50: }
51:
52: int min = Integer.MAX_VALUE;
53:
54: /*
55: * Calculates the minimum number of strokes for all possible
56: * combinations of sub-strings to the right of the current position.
57: * In the first pass, the first call to calculateMinStrokes will be
58: * empty, and the entire remainder of the string will be used in the
59: * second call to calculateMinStrokes. In each subsequent pass, a
60: * character is added to the first call, and removed from the second
61: * call.
62: */
63: for (int i = 1; i <= size; i++) {
64: min = Math.min(min, 1 +
65: calculateMinStrokes(stripes, start + 1, i - 1, stripes.charAt(start)) +
66: calculateMinStrokes(stripes, start + i, size - i, color));
67: }
68:
69: // Store the calculate value to avoid having to calculate it again.
70: alreadySeen[start][size][color - BLANK_COLOR] = min;
71:
72: return min;
73:
74: }
