제약이있는 n 개의 변수가있는 방정식의 솔루션 수

Question

방정식의 해를 계산하려고했으나 아무런 진전을 이끌어 낼 수 없습니다. 방정식은 다음과 같습니다

내가 얻을 수있는 모든 같은 일을하는 것입니다,

하지만이에 진행하는 방법을 모르겠어요.

Answer 1

나는 이것을 dynamic programming을 사용하여 해결하려고합니다.

여기에 당신이 시작하는 일부 의사 코드는 다음과 같습니다

Procedure num_solutions(n, k, m): 
    # Initialize memoization cache: 
    if this function has been called for the first time: 
    initialize memo_cache with (n+1)*(k+1)*(m+1) elements, all set to -1 

    # Return cached solution if available 
    if memo_cache[n][k][m] is not -1: 
    return memo_cache[n][k][m] 

    # Edge case: 
    if m is equal to 1: 
    # Solution only exists if 1 <= m <= k 
    if n >= 1 and n <= k, set memo_cache[n][k][m] to 1 and return 1 
    otherwise set memo_cache[n][k][m] to 0 and return 0 

    # Degenerate case: No solution possible if n<m or n>k*m 
    if n < m or n > k * m: 
    set memo_cache[n][k][m] to 0 and return 0 

    # Call recursively for a solution with m-1 elements 
    set sum to 0 
    for all i in range 1..k: 
    sum = sum + num_solutions(n - i, k, m - 1) 

    set memo_cache[n][k][m] to sum and return sum