用斐波那契数的和来计算一个数的表示数

Question

function F(n:Integer):Integer;

我认为第一个不可避免的步骤是做一个n个斐波那契数的数组，如下所示：

Fib[1]:=1;
Fib[2]:=1;
for i:=3 to n do
    Fib[i]:=Fib[i-1]+Fib[i-2];

当然，我们可以通过只计算那些小于或等于n的斐波那契数来优化它，但这没有多大帮助，因为动态数组是不允许的。那么我们如何才能避免指数级的时间复杂度呢？

Answer 1

让我们来证明一些关于数字的东西：

引理1：设n≥1为整数，Fib(i)为最大Fibonacci数且Fib(i)≤n。然后，在n表示为具有不同指数的斐波那契数之和时，出现Fib(i)或Fib(i-1)，但不是两者都出现。

证明：我们可以通过归纳法证明Fib(1)+Fib(2)+...+Fib(i-2)=Fib(i)-1之和。由于Fib(i) n（否则Fib(i)将不是小于或等于n的最大Fibonacci数）。

function F(n : Integer, recurseHigh = True: Bool):
    if n == 0: return 1
    a, b = 1, 1
    while a + b <= n:
        a, b = b, a + b
    res = 0
    if recurseHigh: res += F(n - b)
    res += F(n - a, n - a < a)
    return res

F(0) = 1
F(1) = 2
F(2) = 2
F(3) = 3
F(4) = 3
F(5) = 3
F(6) = 4
F(7) = 3
F(8) = 4
F(9) = 5
F(10) = 4
F(11) = 5
F(12) = 4
F(13) = 4
F(14) = 6
F(4079078553298575003715036404948112232583483826150114126141906775660304738681982981114711241662261246) = 70875138187634460005150866420231716864000000
F(2093397132298013861818922996230028521104292633652443820564201469339117288431349400794759495467500744) = 157806495228764859558469497848542003200000000
F(1832962638825344364456510906608935117588449684478844475703210731222814604429713055795735059447061144) = 9556121706647393773891318116777984000000000
F(6529981124822323555642594388843027053160471595955101601272729237158412478312608142562647329142961542) = 7311968902691913059222356326906593280000000
F(3031139617090050615428607946661983338146903521304736547757088122017649742323928728412275969860093980) = 16200410965370556030391586130218188800000000
F(4787808019310723702107647550328703908551674469886971208491257565640200610624347175457519382346088080) = 7986384770542363809305167745746206720000000
F(568279248853026201557238405432647353484815906567776936304155013089292340520978607228915696160572347) = 213144111166298008572590523452227584000000000
F(7953857553962936439961076971832463917976466235413432258794084414322612186613216541515131230793180511) = 276031486797406622817346654015856836608000000
F(2724019577196318260962320594925520373472226823978772590344943295935004764155341943491062476123088637) = 155006702456719127405700915456167116800000000
F(4922026488474420417379924107498371752969733346340977075329964125801364261449011746275640792914985997) = 3611539307706585535227777776416785118003200
F(10^1000) = 1726698225267318906119107341755992908460082681412498622901372213247990324071889761112794235130300620075124162289430696248595221333809537338231776141120533748424614771724793270540367766223552120024230917898667149630483676495477354911576060816395737762381023625725682073094801703249961941588546705389069111632315001874553269267034143125999981126056382866927910912000000000000000000000000000000000000000000000000000000000000000000000000000000

更新：这里是Python代码：

memo = {}
def F(n, x=True):
    if n == 0: return 1
    if (n, x) in memo: return memo[n,x]
    i = 1
    a, b = 1, 1
    while b + a <= n:
        a, b = b, a + b
    memo[n,x] = (F(n - b) if x else 0) + F(n - a, n - a < a)
    return memo[n,x]

更新2：使用二分搜索查找i并使用快速矩阵求幂运算计算Fib(i),即使不需要记忆,也可以获得更好的运行时。但可能不值得这么做，特别是对于32位n。

更新3：为了好玩，这里有一个实现，可以证明它只做o（log n)添加：

fib = [0,1]
def greedy(n):
    while fib[-1] < n:
        fib.append(fib[-1] + fib[-2])
    i = 1
    while fib[i+1] <= n: i += 1
    digs = set()
    while n:
        while fib[i] > n: i -= 1
        digs.add(i)
        n -= fib[i]
    return digs

def F(n):
    digs = greedy(n)
    top = max(digs)
    dp = [[[0,0,0] for _ in xrange(4)] for _ in xrange(top+1)]
    for j in xrange(0, 2): dp[0][j][0] = 1
    for i in xrange(1, top + 1):
        for j in xrange(0,2):
            for k in xrange(0,j+1):
                if i in digs:
                    dp[i][j][k] = dp[i-1][k+j][j] + dp[i-1][k+j+1][j+1]
                else:
                    dp[i][j][k] = dp[i-1][k+j][j] + dp[i-1][k+j-1][j-1]
    return dp[top][0][0]