题目114：用至少三个单位长的相分割的木板填充一行共有多少种方法？

欧拉计划

Counting block combinations I

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).

题目：

一条长度为 7 的行上放有最小长度为 3 的红色块，要求相邻的两个红色块（长度可不相同）之间至少用一个黑色块相分割。要达到这个目的一共有 17 种方式。

按照上述要求填充长度为 50 的行共有多少种方式？

注意：虽然上面的例子并未阐明，但是不同长度的块是可以放在一起的。例如，如果行的长度是 8，可以用长度为 3 的红色块，长度为 1 的黑色块和长度为 4 的红色块来填充。

jerryxjr1220

递归+动态规划

records = [0]*100
def F(m,n=3):
    global records
    solutions = 1
    if n>m: return solutions
    if records[m] != 0: return records[m]
    for i in range(m-n+1):
        for j in range(n,m-i+1):
            solutions += F(m-i-j-1, n)
    records[m] = solutions
    return solutions
print(F(50))

16475640049

guosl

/*
答案：16475640049
*/
#include <iostream>
using namespace std;

//f[i][0]表示长度为i的格子的填充方式数，且最后一个格子用黑色填充
//f[i][1]表示长度为i的格子的填充方式数，且最后一个格子用红色填充
long long f[51][2];

int main(void)
{
  f[1][0] = 1;
  f[2][0] = 1;
  f[0][0] = 1;
  for (int i = 3; i <= 50; ++i)
  {
    f[i][0] = f[i - 1][0] + f[i - 1][1];//在长度为i-1的基础上加上一块黑格子
    for (int k = 3; k <= i; ++k)
      f[i][1] += f[i - k][0];//在长度为i-k，且最后一个格子为黑色的基础上加上一个长度为k的红色块
  }
  cout << f[50][0] + f[50][1] << endl;
  return 0;
}