確定了一些可能的組合的數量得到一個特定的結果

Question

我碰到這個問題就來了：

給定一個整數，確定可能的組合只用2,3,7，其總和將給予整數數量。

例如：

4 - 2 {(2,2)} 
9 - 3 {(2, 7), (2, 2, 2, 3), (3, 3, 3)} 

的一種方式是通過3個環迭代，然後確定該和是否是可以實現的。這裏的代碼：

for(i=0; i<=num/2; i++){ 
    for(j=0; j<=num/3; j++){ 
     for(k=0; k<=num/7; k++){ 
      if(i*2+j*3+k*7 == num) 
       count++; 
} 

這裏計數將有可能的數量。但這是非常低效的，需要O（n3）時間。我想知道是否有其他有效的方法來計算不同組的數量。

Answer 1

對於這個問題，dp解決方案應該是線性的。 （Implemented here）

#include <stdio.h> 
#define SZ 5 
int memo[SZ+1+7]; 


int main(void) { 
    int i = 0; 
    memset(&memo[0], 0, sizeof memo); 
    memo[0] = 1; 

    for(i = 0; i <= SZ; ++i) memo[i+2] += memo[i]; 
    for(i = 0; i <= SZ; ++i) memo[i+3] += memo[i]; 
    for(i = 0; i <= SZ; ++i) memo[i+7] += memo[i]; 

    printf("%d\n", memo[SZ]); 

    return 0; 
} 

1. 我們從一個1-d DP陣列memo與大小的理想情況下infinited大小 （在實踐中動態分配），這不會導致超出界限 索引SZ + max_num。
2. 將此數組的元素0與1進行初始化，因爲有1路 來獲取empty_sum。
3. 如果我們可以用x種方式獲得k的數字，則有更多的方法可用 獲得k+2,k+3和k+7。這是3個循環使用的。 （Number_of_ways [{2,3,7} + 1] + = number_of_ways [I]）
4. 畢竟環完成後，備忘錄[K：0 - SZ]包含的 方式我們可以獲得K數。

給出複雜度爲O（k * N），其中k爲3（2,3,7）。對於常數k，這是線性的。

Answer 2

這可以在O（n^2）中解決。

只是爲了避免你的最後一個循環。

for(i=0; i<=num/2; i++){ 
    for(j=0; j<=num/3; j++){ 
     k = num - i*2 - j*3; 
     if(k%7==0) 
       count++; 
    } 
}