由0,1,2组成的长度为n的序列,所有元素总和为偶数的序列有多少?

解题思路,可以设F[i][j]表示长度为i的序列总和对2的余数是j的情况有多少种
那么f[i][j]=f[i-1][1-j]+f[i-1][j]*2
是这么个递推公式,你说的递归是直接枚举有哪些序列吗?然后把这些序列的数字加起来看看是不是偶数这样吗?那样的复杂度很高的,有3^n次方
#include
#include
const int MAX=20;
int ans[MAX][2]={0};
int main(void)
{
int i,j;
int n;
ans[0][0]=1;
for(i=1;i不是编程的问题，就是用普通的数学计算方法，比如 T(n)=T(n-1)+T(n-2)， 类似这种的方法恩，我已经用了数学计算的公式了，我这样好理解一些，你说的是化成一维的吧，我的复杂度其实也是O（n）的，因为第二维只有两个不好意思哈~我真的很不理解这种递归的解法，你说的这个二维的我更加看不懂 了。。能不能麻烦你化成一维的？如果能稍微解释一下就更好了！谢谢二维好理解一些的 其实这是一个动态归划的思想 因为你想算长度N，那么我们可以先算出长度为N-1的嘛 那么长度为N的和N-1的有什么关系呢？ 因为题目里面说的是奇偶数，那么我们可以再加一维状态是这N个数字之和是奇数还是偶数 那么长度为N的时候加起来是奇数的情况的种数记为F[n][0] 是奇数的情况记为F[n][1] 假设已知F[n-1][0] F[n-1][1]是多少，怎么推出 F[n][0] F[n][1]呢？ 我们可以这么想，F[n][0]可以由F[n-1][0],F[n-1][1]通过某种转化过来 那么我们看看是什么个关系的转化 F[n-1][0]这个是偶数的情况，加一个什么数字可以到长度为N的偶数呢？ 当然是再加一个偶数啦，这里的偶数有0，2两种，所以F[n][0]是要加上F[n-1][0]*2的 那么F[n-1][1]如何转化到F[n][0]呢？ 当然是再加一个奇数，这里奇数只有一个，所以F[n][0]要加上F[n-1][1] 所以F[n][0]=f[n-1][1]+F[n-1][0]*2 F[n][1]的情况类似分析 F[n][1]=f[n-1][1]*2+F[n-1][0] 这样就可以由n-1的长度推到n的长度，那么 F[0][0]=1 F[0][1]=1 这个是已知的，是不是可以由N次的循环求出F[n][0],f[n][1]啦 最后我们要的答案是F[n][0] 报赚上面的程序有一些错了，忘加一句话 #include #include const int MAX=20; int ans[MAX][2]={0}; int main(void) {int i,j;int n;ans[0][0]=1;for(i=1;i