Counting block combinations I题号：114 难度： 35 中英对照

A row measuring seven units in length has red blocks with a minimum length of three units placed on it, such that any two red blocks (which are allowed to be different lengths) are separated by at least one black square. There are exactly seventeen ways of doing this.

How many ways can a row measuring fifty units in length be filled?

NOTE: Although the example above does not lend itself to the possibility, in general it is permitted to mix block sizes. For example, on a row measuring eight units in length you could use red (3), black (1), and red (4).

Code


public final class p114 {
public static void main(String[] args) {
long start=System.nanoTime();
String result = run();
long end=System.nanoTime();
System.out.println(result);
System.out.println( (end-start)/1000000 + "ms" );
}

static public long dp[][]=new long[55][2];
static public String run(){
for(int i=0;i<=2;i++){
dp[i][0]=1;
dp[i][1]=0;
}
dp[3][0]=1;//black
dp[3][1]=1;//red
int ans=50;
for(int i=4;i<=ans;i++){
dp[i][0]=dp[i-1][0]+dp[i-1][1];
dp[i][1]=0;
for(int j=3;j<=i;j++)
dp[i][1]+=dp[i-j][0];
}
return Long.toString(dp[ans][0]+dp[ans][1]);
}

}
16475640049
0ms