我遇到了以下演算法問題，它對運行時有嚴格的限制（<10s 并且沒有大的記憶體占用），我很難過。我的方法失敗了一半的測驗用例。
問題
一個盒子包含許多專案，一次只能洗掉 1 個或一次只能洗掉 3 個。
有多少種方法可以清空盒子？答案可能非常大，因此以 10^9 7 的模數回傳。
例如，最初有 n=7 個專案。它們可以通過九種方式洗掉，如下所示：
1.(1,1,1,1,1,1,1)
2.(1.1.1.1.3)
3.(1,1,1,3,1)
4.(1,1,3,1,1)
5.(1,3,1,1,1)
6.(3,1,1,1,1)
7.(1,3,3)
8.(3,1,3)
9.(3,3,1)
所以函式應該回傳 9。
函式說明：你的函式必須接受一個引數，n表示專案的數量，并回傳一個整數，表示清空盒子的方式數。
約束：1<=n<=10^8
示例案例：
Input: 1
Sample OutPut: 1
Explanation: There is only 1 way to remove 1 item. Answer=(100000007)=1
Input: 7
Sample OutPut: 9
There is only 9 ways to remove 7 items
我的方法
這導致了一個標準的遞回關系，其中f(n) = f(n-3) f(n-1)n > 2，所以我這樣做如下
def memoized_number_of_ways(dic, n):
if n not in dic:
dic[n] = memoized_number_of_ways(dic, n-3) memoized_number_of_ways(dic, n-1)
return dic[n]
def numberOfWays(n):
# Write your code here
memoize = {1:1,2:1,3:2}
import math
ans = memoized_number_of_ways(memoize,n)
return ans % (math.pow(10,9) 7)
然而，這在任何情況下都會失敗n > 10**2。你怎么能在沒有太多記憶體的情況n下10^8在不到 10 秒的時間內解決這個問題？
uj5u.com熱心網友回復：
只需使用矩陣撰寫您的遞回（請原諒我撰寫矩陣的方式，StackOverflow 不允許 LaTeX）。
[f(n) ] = [1 0 1] [f(n-1) ]
[f(n-1)] = [1 0 0] [f(n-2) ]
[f(n-2)] = [0 1 0] [f(n-3) ]
現在您所要做的就是將一個 3x3 矩陣（模固定常數）提高到 n 的冪（或 n-3 或類似的東西，取決于您的“基本情況列向量”，填寫詳細資訊），然后將其乘以“基本情況列向量”。這可以在 O(logn) 時間內完成。
PS：您可能需要查找矩陣 exponentiation。
uj5u.com熱心網友回復：
三種解決方案，對于tio.run（具有中速計算機）上的 n=10 8，最快需要大約 31 μs 。
一個矩陣冪的解決方案，像avoriteofnone 所描述的，大約需要 1 毫秒（在線試用！）：
import numpy as np
from time import time
class ModInt:
def __init__(self, x):
self.x = x % (10**9 7)
def __add__(a, b):
return ModInt(a.x b.x)
def __mul__(a, b):
return ModInt(a.x * b.x)
def __str__(self):
return str(self.x)
def solve(n):
O = ModInt(0)
I = ModInt(1)
A = np.matrix([[O,I,O], [O,O,I], [I,O,I]])
return (A**n)[2,2]
for _ in range(3):
t0 = time()
print(solve(10**8), time() - t0)
輸出（n=10 8的結果和時間，以秒為單位，三次嘗試）：
109786077 0.0010712146759033203
109786077 0.0010180473327636719
109786077 0.0009677410125732422
另一個，大約需要 0.5 毫秒（在線嘗試！）：
import numpy as np
from time import time
def solve(n):
A = np.matrix([[0,1,0], [0,0,1], [1,0,1]])
power = 1
mod = 10**9 7
while n:
if n % 2:
power = power * A % mod
A = A**2 % mod
n //= 2
return power[2,2]
for _ in range(3):
t0 = time()
print(solve(10**8), time() - t0)
一個基于@rici 在評論中的解決方案，大約需要 31 μs（在線試用！）：
from timeit import repeat
def solve(n):
m = 10**9 7
def abc(n):
if n == 0:
return 0, 1, 0
a, b, c = abc(n // 2)
d = a c
e = b d
A = 2*a*b c*c
C = 2*b*c d*d
E = 2*c*d e*e
D = A C
B = E - D
if n % 2:
A, B, C = B, C, D
return A%m, B%m, C%m
return sum(abc(n)) % m
n = 10**8
print(solve(n))
for _ in range(3):
t = min(repeat(lambda: solve(n), 'gc.enable()', number=1000)) / 1000
print('%.1f μs' % (t * 1e6))
說明：查看我之前解決方案中的矩陣冪，我注意到它們實際上只包含五個不同的值，并且它們是我們所需序列中的連續結果數字。例如，A**19是：
[[277 189 406]
[406 277 595]
[595 406 872]]
我按遞增順序給他們起名字：
| b a c |
| c b d |
| d c e |
對該矩陣求平方會得到一個更大的矩陣，其中包含條目 A/B/C/D/E。如果你對上面的矩陣求平方，你會發現關系A = 2*a*b c*c等等。
我的輔助函式abc(n)計算第 n 個矩陣冪的條目 a/b/c。對于 n=0，這是單位矩陣，所以我的 a/b/c 是 0/1/0。最后I，回傳e值（計算為e=b d=a b c）。
uj5u.com熱心網友回復：
這是一個簡單的迭代 O(n) 時間 / O(1) 空間解決方案，其優化版本在中速機器上需要 6 秒（未優化需要 15 秒）。
未優化（在線嘗試！）：
def solve(n):
mod = 10**9 7
a = b = c = 1
for _ in range(n):
a, b, c = b, c, (a c) % mod
return a
print(solve(7))
print(solve(10**8))
優化（在線試用！）：
def solve(n):
mod = 10**9 7
a = b = c = 1
for _ in range(n // 300):
for _ in range(100):
a = c
b = a
c = b
a %= mod
b %= mod
c %= mod
for _ in range(n % 300):
a, b, c = b, c, (a c) % mod
return a
uj5u.com熱心網友回復：
您的解決方案在正確的軌道上，并且該錯誤與您的演算法無關（是的）。
問題是當您對一些大數字執行操作時，您會失去精度。請注意，您可以mod 10 ** 9 7沿代碼應用，因為添加不受它的影響。通過這樣做，您可以將所有數字保持在一定大小以下，并且不會有任何浮點精度錯誤：
import math
def memoized_number_of_ways(dic, n):
if n not in dic:
dic[n] = (memoized_number_of_ways(dic, n-3) memoized_number_of_ways(dic, n-1)) % (math.pow(10,9) 7)
return dic[n]
def numberOfWays(n):
memoize = {1:1,2:1,3:2}
ans = memoized_number_of_ways(memoize,n)
return ans
請注意，為了讓您能夠回答問題，n > 1000您需要解決此遞回錯誤問題。
不幸的是，即使是一個非常有效的解決方案（提示：你的字典中任何時候都不需要超過 3 個專案）也不會n ~ 10 ** 9在一秒鐘內解決這個問題。而且您將需要找到另一種方法-這里的第二個答案是一個不錯的選擇:)
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/486303.html
上一篇：使用回溯生成給定陣列的排列