問(wèn)題

有這樣一個(gè)關(guān)于臺(tái)階和步數(shù)的題目：

假設(shè)A上臺(tái)階，一次可以跨1層，2層，3層.. 或m層，問(wèn)A上n層臺(tái)階，有多少種走法？其中，m和n都是正整數(shù)，并且 m <= n

對(duì)臺(tái)階步數(shù)問(wèn)題提出簡(jiǎn)單分析，探索是否存在更優(yōu)解的方案。

分析

這個(gè)問(wèn)題等價(jià)于：

對(duì)于數(shù)n，有多少種方案讓小于n的數(shù)相加等于n，且這些數(shù)中的***數(shù)不超過(guò)m(m<=n) 

首先考慮m=n時(shí)情況

有多少種方案把n拆分成1...n份：

當(dāng)n=2時(shí)，分1種{2}，分2種{1*2}

當(dāng)n=3時(shí)，分1種{3}，分2種[1,2]的排列，分3種{1*3}

當(dāng)n=4時(shí)，分1種{4}，分2種[1,3][2,2]的排列，分3種[1,1,2]的排列，分4種{1*4}

當(dāng)n=5時(shí)，分1種{5}，分2種[1,4][2,3]的排列，分3種[1,1,3][1,2,2]的排列，分4種[1,1,1,2]的排列，分5種{1*5}

當(dāng)n=6時(shí)，分1種{6}，分2種[1,5][2,4][3,3]的排列，分3種[1,1,4][1,2,3][2,2,2]的排列，分4種[1,1,1,3][1,1,2,2]的排列，分5種[1,1,1,1,2]的排列，分6種1*6

……

于是每一步分法都是一個(gè)將整數(shù)n的進(jìn)行有序k分拆問(wèn)題。

根據(jù)組合數(shù)學(xué)定理：正整數(shù)n的有序k分拆的個(gè)數(shù)等于。即(n-1)選(k-1)的組合數(shù)。

這正是楊輝三角的第n行第k項(xiàng)的通項(xiàng)：

于是，可以得到：

那么 k→1...n 總方案數(shù)(即為n從1拆分到n拆分的和的函數(shù)，用S(n)記號(hào)表示)

   （根據(jù)楊輝三角性質(zhì)）

考慮1<m<n的情況：

(非常抱歉因疏于嚴(yán)謹(jǐn)上一版中該部分推測(cè)有誤，經(jīng)查證后給出準(zhǔn)確方法。特別感謝 @張晉坤 @顧健 等同學(xué)的斧正。)

當(dāng)m<n時(shí)，該問(wèn)題可以描述為，設(shè)k施一個(gè)給定的正整數(shù)，設(shè)h_k(n)表示將正整數(shù)n拆分分部量只含1,2,3...k的有序分拆數(shù)。該問(wèn)題符合廣義斐波那契數(shù)定義，則h_k(n)滿足：

當(dāng)n<=k時(shí)，h_k(n)=2^n-1

當(dāng)n>k>=2時(shí)，h_k(n)=h_k(n-1)+h_k(n-2)+...+h_k(n-k)

因?yàn)閚<=k時(shí)，正整數(shù)n拆成分部量只含1,2..k的有序分拆數(shù)，就是n的有序分拆數(shù)，而n得有序分拆數(shù)就是2^n-1。

所以，根據(jù)定理寫出了此迭代的循環(huán)版本，如下面的wideFib方法。 

總結(jié)

以上總結(jié)，可以用一分段函數(shù)來(lái)描述這個(gè)問(wèn)題的通解： 

當(dāng)m=n時(shí)復(fù)雜度為O(1)

當(dāng)m<n時(shí)復(fù)雜度為O(nm+n)，雖然未能達(dá)到線性復(fù)雜度，但也能看出具有更小的常數(shù)階。

所以有一定程度的優(yōu)化改善。

示例

利用上面的結(jié)論，給出如下代碼：

//java  
    
    static long stepsOfTerrace(int n, int m) {  
        if (m > n || n < 2)  
            throw new IllegalArgumentException();  
        if (m == n)  
            return (long) Math.pow(2, n - 1);  
        else if (m > 1)  
            return wideFib(n , m);  
        else 
            return n;  
    }  
 
    static long wideFib(int n, int k) {  
        long[] steps = new long[n];  
        for (int i = 1; i <= n - 1; i++) {  
            if (i <= k)    // hk(k)之前序列=2^n-1  
                steps[i] = (int) Math.pow(2, i - 1);  
            else    // 之后按照廣義斐波那契計(jì)算  
                for (int j = i - 1; j >= i - k; j--)  
                    steps[i] += steps[j];  
        }  
        long sum = 0;  
        for (int i = n - k; i <= n - 1; i++)  
            sum += steps[i];  
        return sum;  
    }   

原文鏈接：http://my.oschina.net/spance/blog/229477