when n = 1
S(1) = 1;
when n = 2, there are two combinations
2 = 2
2 = 1 1
S(2) = 2;
when n = 3, there are 3
3 = 3
3 = 1 1 1
3 = 1 2
S(3) = 3
4 = 4
4 = 1 1 1 1
4 = 2 1 1
4 = 2 2
4 = 3 1
S(4) = 5
…………
當 n <= 1000 時，如何計算 S(n)？我提出了一個蠻力 dfs 解決方案，這是 python 中的代碼：
class S1:
def __init__(self):
self.cnt = 1
def dfs(self, begin, n, remain):
if n == 1: return
if remain == 0:
self.cnt = 1
return
if remain < 0:
return
for i in range(begin, n):
self.dfs(i, n, remain - i)
還有其他一些不使用遞回并且時間復雜度較小的方法嗎？
uj5u.com熱心網友回復：
解決方案在于定義一個函式f(s, d)，對應于 sum 的組合數s，最大位數等于或小于d。
然后，我們可以使用遞回關系
f(s, d) = f(s, d-1) f(s-d, d)
第一項f(s, d-1)對應于所有項小于或等于 的組合，d-1第二項f(s-d, d)對應于至少一個元素等于 的情況d。
必須注意一些特殊值：
f(s, 1) = 1
if (d > s) then f(s, d) = f(s, s)
f(0,d) = 1
這可以以迭代的方式實作。這可以等效地以遞回方式實作。但是，在后一種情況下，重要的是使用記憶以避免多次計算相同的值。
最終答案等于
S(n) = f(n, n)
總復雜度為 O(n^2)，對于最大尺寸應該足夠了n = 1000。
下面是 C 中的一個實作，用于說明該演算法。例如n = 1000，解決方案在大約 10 毫秒內提供。
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
std::string toString(__int128 num) {
auto neg = num < 0;
if (neg) num = -num;
std::string str;
do {
int digit = num % 10;
str = std::to_string(digit);
num /= 10;
} while (num != 0);
std::string rev;
if (neg) rev = "-" std::string (str.rbegin(), str.rend());
else rev = std::string (str.rbegin(), str.rend());
return rev;
}
int main() {
std::cout << "enter n: ";
int n;
std::cin >> n;
std::vector<std::vector<__int128>> sums (n 1, std::vector<__int128> (n 1));
for (int d = 0; d <= n; d ) {
sums[0][d] = 1;
}
for (int sum = 1; sum <= n; sum ) {
sums[sum][1] = 1;
for (int d = 2; d <= sum; d ) {
int dp = std::min (sum-d, d);
sums[sum][d] = sums[sum][d-1] sums[sum-d][dp];
}
}
std::cout << "S[" << n << "]= " << toString(sums[n][n]) << "\n";
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/478622.html