题目描述
有一个3*n的数组。3行，n列。在数组中至少填充一个1。
每个1上下左右4周只能填充0。 有多少种数字填充方案
为防止答案过大，答案对1e9+7取模。
输入
1
输出
4
说明
只有1列。这一列的种法可能是[1,0,0],[0,1,0],[0,0,1],[1,0,1]四种
思路，对于任意一列 其只能是000 001 010 100 101 五种方案。
采用dp[i][5] 表示第i列依次为上诉5种方案的数量
以dp[i][3]为例其为100 那么前一列只能为000 001 010
即：dp[i][3]=dp[i][0]+dp[i][1]+dp[i][2]
最后求出dp[n-1]各种情况之和 减去 1 即所有都为0的情况
int solve(int n){// write code herevector<vector<long long>> dp(n,vector<long long>(5,0));//dp[i][0]表示第i列为000 情况 //dp[i][1]表示第i列为001 情况 //dp[i][2]表示第i列为010 情况 //dp[i][3]表示第i列为100 情况 //dp[i][4]表示第i列为101 情况 int m=1e9+7;dp[0][0]=dp[0][1]=dp[0][2]=dp[0][3]=dp[0][4]=1;for(int i=1;i<n;i++){//第i列为000 情况 那么前一列可以为5种情况dp[i][0]=(dp[i-1][0]+dp[i-1][1]+dp[i-1][2]+dp[i-1][3]+dp[i-1][4])%m;dp[i][1]=(dp[i-1][0]+dp[i-1][2]+dp[i-1][3])%m;dp[i][2]=(dp[i-1][0]+dp[i-1][1]+dp[i-1][3]+dp[i-1][4])%m;dp[i][3]=(dp[i-1][0]+dp[i-1][1]+dp[i-1][2])%m;dp[i][4]=(dp[i-1][0]+dp[i-1][2])%m; }return (dp[n-1][0]+dp[n-1][1]+dp[n-1][2]+dp[n-1][3]+dp[n-1][4]-1)%m;}上诉代码可以进一步空间优化为 因为第k次计算只会用到k-1次的结果。