那么f[i][j]=f[i-1][1-j]+f[i-1][j]*2
是這么個遞推公式,你說的遞歸是直接枚舉有哪些序列嗎?然后把這些序列的數(shù)字加起來看看是不是偶數(shù)這樣嗎?那樣的復(fù)雜度很高的,有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不是編程的問題，就是用普通的數(shù)學(xué)計(jì)算方法，比如 T(n)=T(n-1)+T(n-2)， 類似這種的方法恩，我已經(jīng)用了數(shù)學(xué)計(jì)算的公式了，我這樣好理解一些，你說的是化成一維的吧，我的復(fù)雜度其實(shí)也是O（n）的，因?yàn)榈诙S只有兩個不好意思哈~我真的很不理解這種遞歸的解法，你說的這個二維的我更加看不懂 了。。能不能麻煩你化成一維的？如果能稍微解釋一下就更好了！謝謝二維好理解一些的 其實(shí)這是一個動態(tài)歸劃的思想 因?yàn)槟阆胨汩L度N，那么我們可以先算出長度為N-1的嘛 那么長度為N的和N-1的有什么關(guān)系呢？ 因?yàn)轭}目里面說的是奇偶數(shù)，那么我們可以再加一維狀態(tài)是這N個數(shù)字之和是奇數(shù)還是偶數(shù) 那么長度為N的時候加起來是奇數(shù)的情況的種數(shù)記為F[n][0] 是奇數(shù)的情況記為F[n][1] 假設(shè)已知F[n-1][0] F[n-1][1]是多少，怎么推出 F[n][0] F[n][1]呢？ 我們可以這么想，F(xiàn)[n][0]可以由F[n-1][0],F[n-1][1]通過某種轉(zhuǎn)化過來 那么我們看看是什么個關(guān)系的轉(zhuǎn)化 F[n-1][0]這個是偶數(shù)的情況，加一個什么數(shù)字可以到長度為N的偶數(shù)呢？ 當(dāng)然是再加一個偶數(shù)啦，這里的偶數(shù)有0，2兩種，所以F[n][0]是要加上F[n-1][0]*2的 那么F[n-1][1]如何轉(zhuǎn)化到F[n][0]呢？ 當(dāng)然是再加一個奇數(shù)，這里奇數(shù)只有一個，所以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次的循環(huán)求出F[n][0],f[n][1]啦 最后我們要的答案是F[n][0] 報賺上面的程序有一些錯了，忘加一句話 #include