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))
(not able to follow the comments mentioned here).