核电站问题-题解(试着解释下f[i]=2*f[i-1]-f[i-4])

拿到题目感觉不太会，看了下优秀小伙伴儿们的题解，对其中这个通解公式不是很理解，想了很久之后觉得大概可以这样解释，故写出来跟大家分享，也请各位指教。首先代码：

#include<stdio.h>
#include<string>
#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;
const int INF=0x3f3f3f3f, maxn=10005;

int main()
{
	int n,f[45];
	f[0]=1;//0个坑只有一种不放的可能
	for(int i=1;i<=40;i++)
	{
		if(i<3)
			f[i]=2*f[i-1];
		else if(i==3)
			f[i]=2*f[i-1]-1;
		else
			f[i]=2*f[i-1]-f[i-3-1];
	} 
	while(cin>>n)
	{
		printf("%d\n",f[n]);
	}
	return 0;
}

我的想法是这样的：题目要求不能连续三个坑都放入核物质，那么当n<3时无论怎么放都不会爆炸。可以这样理解，1个坑有放或者不放2种选择，那么每多一个坑就是在n-1的基础上选择对这个坑放或不放2种选泽，所以有f[i]=2*f[i-1]；当n==3时，由于不能都放就需要减掉1种。

难理解的在于当n>3时，其他大大们给出的公式是：f[i]=2*f[i-1]-f[i-4]，哎嘛这是咋来的！在这里分享一下我的个人理解，也请大家批评指正。我认为当n>3时，每增加一个坑位我们需要考虑的就是在2*f[i-1]的基础上减掉那些不合规的，那不合规的原因只有新增了坑位选择放，而n-1、n-2连续两个已经放了（这说明第n-3肯定不会放，因为放了就连续三个了~），所以我们需要减掉这种情况，那这种情况不就应该是n-1、n-2放，n-3不放，前面任意嘛（前面的一定是符合规定的，不会存在连续放的情况呀），所以我们就减掉f[i-4]啦。

拿f[5]举个例子：☆ ☆ ☆ ☆ ☆，五个坑位

我们在计算f[5]时可以在f[4]的基础上先×2，因为第5个坑可以选择放or不放。但如果选择放问题就来啦，可能出现这种情况 ☆ ☆ ★ ★ ★，所以要想办法减掉。如果第3个坑和第4个坑一定要放，那么f[4]中我们知道第2个坑肯定不能放（放了就连续3个了呢！）所以其实只有第一个坑是任意的，也就只需要减掉f[1]了。

那么进而再推一步，如果是n个坑位，连续m个坑放入核物质会爆炸，只需要将n>m的部分修正为f[i]=2*f[i-1]-f[i-m-1]就可以啦~

-------------------------------------------------------

第一次分享题解，以后会继续坚持滴！