小编Abr*_*led的帖子

我一直在努力解决这个编程问题,但由于我无法理解,我在网上找到了一个解决方案.但我真的不明白为什么这个解决方案有效..

任务是计算3*n(n >= 0,n是唯一输入)矩形可用多少种方式完全填充2*1多米诺骨牌.

例如(红线代表多米诺骨牌):

这是我在阅读文本时首先在一张纸上绘制的内容,我看到3*2矩形可以有三种可能的组合,如果n是奇数,则解是0,因为没有办法然后填满整个矩形(一块将始终被多米诺骨牌覆盖).

所以我认为解决方案很简单3^n,如果n是偶数,并且0,如果n是奇数.原来,我错了.

我发现了一个相对简单的解决方案:

#include <iostream>

using namespace std;

int main()
{
    int arr[31];

    arr[0]=1;
    arr[1]=0;
    arr[2]=3;
    arr[3]=0;

    for(int i = 4; i < 31; i++) {
        arr[i] = arr[i-2] * 4 - arr[i-4]; //this is the only line i don't get
    }

    int n;

    while(1) {
        cin >> n;

        if(n == -1) {
            break;
        }

        cout << arr[n] << endl;
    }

    return 0;
}

为什么这样做？!