当前位置:首页 » Project Euler » 详细页

Red, green, and blue tiles 题号:117 难度: 35 中英对照

Using a combination of black square tiles and oblong tiles chosen from: red tiles measuring two units, green tiles measuring three units, and blue tiles measuring four units, it is possible to tile a row measuring five units in length in exactly fifteen different ways.

 

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

NOTE: This is related to Problem 116.


Solution

动态规划。 用$dp[i]$表示长度为$i$的块组成一行的方案数,则该dp对答案的贡献为$dp[50]$。 初始条件为$dp[0]=1$。 递推为$dp[i]=dp[i-1]+dp[i-2]+dp[i-3]+dp[i-4]$。 因为题目说明可以组成全黑的一行,所以不需要减一。

Code


public final class p117 {
    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 String run(){
    	final int N=50;
		long[] dp=new long[N+1];
		dp[0]=1;
		for(int i=1;i<=N;i++){
			dp[i]=0;
			for(int j=1;j<=4&&j<=i;j++){
				dp[i]+=dp[i-j];
			}
    	}
    	return Long.toString(dp[50]);
    }
    
}
100808458960497
0ms