藍橋杯快來了，給大家分享一道藍橋杯的題目
題目
小明想知道，滿足以下條件的正整數序列的數量：
- 第一項為 n；
- 第二項不超過 n；
- 從第三項開始，每一項小于前兩項的差的絕對值，
請計算，對于給定的 n，有多少種滿足條件的序列，
【輸入格式】
輸入一行包含一個整數 n，
【輸出格式】
輸出一個整數，表示答案，答案可能很大，請輸出答案除以10000的余數，
【樣例輸入】
4
【樣例輸出】
7
【樣例說明】
以下是滿足條件的序列：
4 1
4 1 1
4 1 2
4 2
4 2 1
4 3
4 4
【評測用例規模與約定】
對于 20% 的評測用例，1 <= n <= 5；
對于 50% 的評測用例，1 <= n <= 10；
對于 80% 的評測用例，1 <= n <= 100；
對于所有評測用例，1 <= n <= 1000，
題解基本思路（看了大家的一些題解，總覺得有些復雜～～）
-
首先從樣例輸出來看，該序列的長度至少為2
-
用遞回列舉的方法來做這道題肯定是很耗時的，所以采用一點動態規劃的思想
-
First, 先考慮長度為2的序列, n1 n2;類似于 1 1，2 1， 2 2這樣，
-
Second, 我們考慮長度為3的序列，從樣例來看，類似于 4 1 1, 4 2 1，4 1 2 這樣的序列；我們只需觀察該序列中的2，3兩位，你會發現有熟悉 1 1, 2 1,他們屬于我們n=1,n=2中符合條件的序列，也就是First中的情況；但是，你也會發現這里誤入了一個 1 2，它似乎就讓我們有點陌生了，
-
Then，我們在考慮長度為4的序列... 哈哈哈,皮一下，其實我們考慮以上兩種情況就足以了，
Summarize
-
剛剛只是給大家引了下路，這里給大家舉個例子，對于給定的數字n，我用f(a，b)表示序列以a,b開頭的序列的個數，如f(1,1)=1, f(4,1)=3，這個可以簡單的筆算出來，
-
規律就是，如果我們想知道所有 以5 2 ...開頭的序列的個數，我們是不是只需要知道以2 1, 2,2開頭的序列的個數和就行了呢?（因為從第三項開始，每一項小于前兩項的差的絕對值）而要知道 2 1, 2,2開頭序列的個數,就可以從第一步輕松得到；即使上升一個較大的數值n，我們也能夠遞推至最小的子問題，只要我們將每種不同開頭的個數儲存起來，就能避免很多的重復運算，接著往下看.
-
在用二維陣列處理時，我們假設 1 2（ 1 4）這樣特殊的"開頭"的序列存在，他們用來儲存 n3<n2 時對應序列的值,這樣就可以和上面統一了，對于如何得到這個值，如求1 4 這樣開頭的序列，我們只需在多處理一步，就又變成了4 1, 4 2這樣我們熟悉的處理了，
python代碼實作
def list_count(n):
'''
動態規劃: 構建 (n+1)*(n+1)整形矩陣
buf[i][j]: (i>=1, j>=1) 表示 i,j..開頭的序列
4 1 2 3
n1 n2 n3 n4
由題：n1 > n2, n3<|n1 -n2|
假設，如果將n1去掉后：n2,n3,n4 也滿足要求
此時存在情況：
1:
n2=n3, buf[n1][n2]=1
2:
n2>n3, buf[n1][n2]=buf[n2][1]+...+buf[n2][ni] (1<i<n2-n3-1)
3:
n2<n3，取｜n2-n3｜, buf[n1][n2]=buf[n3][1]+...+buf[n3][ni] (1<i<|n2-n3|)
'''
buf=[[0 for _ in range(0,n+1)] for _ in range(0,n+1)]
for i in range(1,n+1):
for j in range(1,i+1):
#主處理
if i-j>1:
buf[i][j]+=1
for k in range(1,i-j):
buf[i][j]+=buf[j][k]
else:
buf[i][j]+=1
buf[i][j]%=10000
#輔助處理，計算n3<n2時的值
for x in range(1,i):
buf[x][i]+=1
for y in range(1, abs(x-i)):
buf[x][i]+=buf[i][y]
return sum(buf[n])%10000
如圖：n=5時,buf的值為：
此方陣可以得到所有i<=n的結果，對buf[i]求和
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/276943.html
標籤：其他
上一篇：leetcode 87 擾亂字串
下一篇：高性能計算發展簡史