algorithms – Count number of ways to arrive at sum N given set of numbers >= M


Problem: Count number of ways to arrive at sum N given set of numbers >= M

Inputs: N = 3, M = 1 | Ways: 1 + 1 + 1, 1 + 2, 3 | Output: 3

I could see an ideal solution would be DP (Dynamic Programming) instead of combinations of every pair of numbers.

  • However I find it hard how to start and proceed with the calculations.
  • Looked for existing implementations, can’t find a clear source. Need help.
import numpy as np 
  
# Return number of ways to which numbers 
# that are greater than given number can 
# be added to get sum. 
  
def numberofways(n, m) : 
          
    dp = np.zeros((n + 2, n + 2)) 
      
    dp(0)(n + 1) = 1
  
    # Filling the table. k is for numbers 
    # greater than or equal that are allowed. 
    for k in range(n, m - 1, -1): 
  
        # i is for sum 
        for i in range(n + 1): 
  
            # initializing dp(i)(k) to number 
            # ways to get sum using numbers 
            # greater than or equal k+1 
            dp(i)(k) = dp(i)(k + 1) 
  
            # if i > k 
            if (i - k >= 0): 
                dp(i)(k) = (dp(i)(k) + dp(i - k)(k))
  
    return dp(n)(m) 
  
# Driver Code 
if __name__ == "__main__":
    n, m = (int(i) for i in input().split())
    print(numberofways(n, m)) 
  

References:
https://www.geeksforgeeks.org/different-ways-sum-n-using-numbers-greater-equal-m/

(not able to follow the comments mentioned here).