欧拉项目 | 114 & 115 题 | 染色块的组合数

Problem 114

Problem 115

115题是114题的扩展版本，所以分析115就足够了。

和116 & 117两个题目的思路是一样的，一层一层（也就是砖的下标）向前统计。

不过有两点不同，115题只限制了最小长度$m$，而没有限制最大程度，那么最大程度就是$n$，所有在最后求解满足条件的数量的和下一层灰色的数量的时候，需要从$m$累加到$n$。同时，由于长度不固定，那么在更新每层的颜色的时候，不能几个语句完成而要使用for循环更新所有状态。

下面给出代码，然后在代码里面解释为什么要这么做。

private long F(int m, int n)
{
    int Layer = n;
    int RedBlockLength = Layer;

    // Color: grey[0] or red[1:RedBlockLength]; Layer
    // 二维数组，第一维是颜色，第二位是层（瓷砖的第几块）
    // 最长和瓷砖长度一样，因为没有限制红色砖的长度
    // red[i]表示到某个位置时，红色砖的长度
    // 初始化初始值，第一层的灰色和红色1数量是1，也就是第一块
    // 可以是灰色或者红色
    var reds = new long[RedBlockLength + 1, Layer];
    reds[0, 0] = 1;
    reds[1, 0] = 1;
    for (int i = 2; i <= RedBlockLength; i++)
    {
        reds[i, 0] = 0;
    }

    // 开始遍历每一次
    for (int layer = 1; layer < Layer; layer++)
    {
        long count = 0;
        // 红色砖最短长度是 m，所以从 m 开始先把上一层的值更新以下
        for (int red = m; red <= RedBlockLength; red++)
        {
            count += reds[red, layer - 1];
        }
        count += reds[0, layer - 1]; //add #grey

        // 上一层是灰色或者长度符合条件的红色数量就是下一层灰色可能的个数
        reds[0, layer] = count;

        // 对于本层，红色的第 i+1 块和上一层的第 i 块数量一样
        // 也就是顺着往后接着铺红色
        for (int red = 1; red <= RedBlockLength; red++)
        {
            reds[red, layer] = reds[red - 1, layer - 1];
        }
    }

    // 遍历完成之后，把满足题意得可能性加和起来
    long result = 0;
    for (int red = m; red <= RedBlockLength; red++)
    {
        result += reds[red, Layer - 1];
    }
    result += reds[0, Layer - 1]; //add #grey

    return result;
}