Количество способов разделить число

Question

Дано число N, печать в Сколькими способами он может быть представлен в виде

N = a + b + c + d 

с

1 <= a <= b <= c <= d; 1 <= N <= M 

Мое наблюдение:

For N = 4: Only 1 way - 1 + 1 + 1 + 1 

For N = 5: Only 1 way - 1 + 1 + 1 + 2 

For N = 6: 2 ways  - 1 + 1 + 1 + 3 
         1 + 1 + 2 + 2 

For N = 7: 3 ways  - 1 + 1 + 1 + 4 
         1 + 1 + 2 + 3 
         1 + 2 + 2 + 2 

For N = 8: 5 ways  - 1 + 1 + 1 + 5 
         1 + 1 + 2 + 4 
         1 + 1 + 3 + 3 
         1 + 2 + 2 + 3 
         2 + 2 + 2 + 2 

So I have reduced it to a DP solution as follows: 
DP[4] = 1, DP[5] = 1; 

for(int i = 6; i <= M; i++) 
    DP[i] = DP[i-1] + DP[i-2]; 

Верно ли мое наблюдение или я что-то упускаю. У меня нет тестовых случаев для запуска. Поэтому, пожалуйста, дайте мне знать, правильный подход или неправильный подход.

Answer 1

Неправильно.Вот правильный вариант:

Позволяет DP[n,k] быть представленным числом n как сумма k номеров. Затем вы ищете DP[n,4].

DP[n,1] = 1 
DP[n,2] = DP[n-2, 2] + DP[n-1,1] = n/2 
DP[n,3] = DP[n-3, 3] + DP[n-1,2] 
DP[n,4] = DP[n-4, 4] + DP[n-1,3] 

Я объясню только последнюю строку, и вы сразу увидите, почему другие правдивы.

Возьмем один случай n=a+b+c+d.

Если a> 1, то n-4 = (a-1)+(b-1)+(c-1)+(d-1) является действительной суммой для DP[n-4,4].

Если a = 1, то n-1 = b+c+d является действительной суммой для DP[n-1,3].

Также в обратном направлении:

Для каждого действительного n-4 = x+y+z+t мы имеем действительное n=(x+1)+(y+1)+(z+1)+(t+1).

Для каждого действительного n-1 = x+y+z мы имеем действующий n=1+x+y+z.

Answer 2

Я считаю, что определение функции f (N, m, n), где N - сумма, которую мы хотим произвести, m - максимальное значение для каждого слагаемого в сумме, а n - число членов в сумма должна работать.

f (N, m, n) определено для n = 1 равным 0, если N> m или N в противном случае.

при п> 1, F (N, M, N) = сумма, для всех т от 1 до N из F (St, т, п-1)

Это означает установку каждый термин, правильно налево.

Затем вы можете решить проблему, используя эти отношения, возможно, используя memoization.

Для максимального n = 4 и N = 5000 (и для того, чтобы быстро работать, когда есть 0 возможностей), я думаю, что это, вероятно, достаточно быстро вычислить для большинства целей.

Answer 3

К сожалению, ваш рецидив является неправильным, так как при п = 9, раствор 6, а не 8.

Если р (п, к) есть число способов распределения н в к ненулевому целому числу части, то мы имеем

p(0,0) = 1 
p(n,k) = 0 if k > n or (n > 0 and k = 0) 
p(n,k) = p(n-k, k) + p(n-1, k-1) 

Поскольку имеется либо раздел значения 1 (в этом случае принимать эту часть в стороне дает разбиение п-1 в к-1 часть), или вы можете вычесть 1 из каждого раздела , что дает разбиение n - k. Легко показать, что этот процесс представляет собой биекцию, следовательно, повторяемость.

ОБНОВЛЕНИЕ:

для конкретного случая к = 4, OEIS говорит нам, что существует еще один линейный рецидив, который зависит только от п:

a(n) = 1 + a(n-2) + a(n-3) + a(n-4) - a(n-5) - a(n-6) - a(n-7) + a(n-9) 

Это рекуррентное может быть решена с помощью стандартных методов для получения явной формулы. Я написал небольшую SAGE script, чтобы решить эту проблему и получил следующую формулу:

a(n) = 1/144*n^3 + 1/32*(-1)^n*n + 1/48*n^2 - 1/54*(1/2*I*sqrt(3) - 1/2)^n*(I*sqrt(3) + 3) - 1/54*(-1/2*I*sqrt(3) - 1/2)^n*(-I*sqrt(3) + 3) + 1/16*I^n + 1/16*(-I)^n + 1/32*(-1)^n - 1/32*n - 13/288 

OEIS также gives the following simplification:

a(n) = round((n^3 + 3*n^2 -9*n*(n % 2))/144) 

который я не проверял.

Answer 4

#include <iostream> 

using namespace std; 

int func_count(int n, int m) 
{ 

    if(n==m) 
     return 1; 
    if(n<m) 
     return 0; 
    if (m == 1) 
     return 1; 
    if (m==2) 
     return (func_count(n-2,2) + func_count(n - 1, 1)); 
    if (m==3) 
     return (func_count(n-3,3) + func_count(n - 1, 2)); 

    return (func_count(n-1, 3) + func_count(n - 4, 4)); 
} 

int main() 
{ 

    int t; 
    cin>>t; 
    cout<<func_count(t,4); 
    return 0; 
}