# Different ways to sum n using numbers greater than or equal to m

Given two natural number n and m. The task is to find the number of ways in which the numbers that are greater than or equal to m can be added to get the sum n.

Examples:

```Input : n = 3, m = 1
Output : 3
Following are three different ways
to get sum n such that each term is
greater than or equal to m
1 + 1 + 1, 1 + 2, 3

Input : n = 2, m = 1
Output : 2
Two ways are 1 + 1 and 2
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

The idea is to use Dynamic Programming by define 2D matrix, say dp[][]. dp[i][j] define the number of ways to get sum i using the numbers greater than or equal to j. So dp[i][j] can be defined as:

If i < j, dp[i][j] = 0, because we cannot achieve smaller sum of i using numbers greater than or equal to j.

If i = j, dp[i][j] = 1, because there is only one way to show sum i using number i which is equal to j.

Else dp[i][j] = dp[i][j+1] + dp[i-j][j], because obtaining a sum i using numbers greater than or equal to j is equal to the sum of obtaining a sum of i using numbers greater than or equal to j+1 and obtaining the sum of i-j using numbers greater than or equal to j.

/blockquote>

Below is the implementation of this approach:

## C++

 `// CPP Program to find number of ways to ` `// which numbers that are greater than ` `// given number can be added to get sum. ` `#include ` `#define MAX 100 ` `using` `namespace` `std; ` ` `  `// Return number of ways to which numbers ` `// that are greater than given number can ` `// be added to get sum. ` `int` `numberofways(``int` `n, ``int` `m) ` `{ ` `    ``int` `dp[n+2][n+2]; ` `    ``memset``(dp, 0, ``sizeof``(dp)); ` ` `  `    ``dp[n + 1] = 1; ` ` `  `    ``// Filling the table. k is for numbers ` `    ``// greater than or equal that are allowed. ` `    ``for` `(``int` `k = n; k >= m; k--) { ` ` `  `        ``// i is for sum ` `        ``for` `(``int` `i = 0; i <= n; i++) { ` ` `  `            ``// 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 Program ` `int` `main() ` `{ ` `    ``int` `n = 3, m = 1; ` `    ``cout << numberofways(n, m) << endl; ` `    ``return` `0; ` `} `

## Java

 `// Java Program to find number of ways to ` `// which numbers that are greater than ` `// given number can be added to get sum. ` `import` `java.io.*; ` ` `  `class` `GFG { ` `     `  `    ``// Return number of ways to which numbers ` `    ``// that are greater than given number can ` `    ``// be added to get sum. ` `    ``static` `int` `numberofways(``int` `n, ``int` `m) ` `    ``{ ` `        ``int` `dp[][]=``new` `int``[n+``2``][n+``2``]; ` `         `  `        ``dp[``0``][n + ``1``] = ``1``; ` `      `  `        ``// Filling the table. k is for numbers ` `        ``// greater than or equal that are allowed. ` `        ``for` `(``int` `k = n; k >= m; k--) { ` `      `  `            ``// i is for sum ` `            ``for` `(``int` `i = ``0``; i <= n; i++) { ` `      `  `                ``// 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 Program ` `    ``public` `static` `void` `main(String args[]) ` `    ``{ ` `        ``int` `n = ``3``, m = ``1``; ` `        ``System.out.println(numberofways(n, m)); ` `    ``} ` `} ` ` `  `/*This code is contributed by Nikita tiwari.*/`

## Python3

 `# Python3 Program to find number of ways to ` `# which numbers that are greater than ` `# given number can be added to get sum. ` `MAX` `=` `100` `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 ``=` `3``, ``1` `    ``print``(numberofways(n, m)) ` ` `  `# This code is contributed by Ryuga `

## C#

 `// C# program to find number of ways to ` `// which numbers that are greater than ` `// given number can be added to get sum. ` `using` `System; ` ` `  `class` `GFG { ` ` `  `    ``// Return number of ways to which numbers ` `    ``// that are greater than given number can ` `    ``// be added to get sum. ` `    ``static` `int` `numberofways(``int` `n, ``int` `m) ` `    ``{ ` `        ``int``[, ] dp = ``new` `int``[n + 2, n + 2]; ` ` `  `        ``dp[0, n + 1] = 1; ` ` `  `        ``// Filling the table. k is for numbers ` `        ``// greater than or equal that are allowed. ` `        ``for` `(``int` `k = n; k >= m; k--) { ` ` `  `            ``// i is for sum ` `            ``for` `(``int` `i = 0; i <= n; i++) { ` ` `  `                ``// 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 Program ` `    ``public` `static` `void` `Main() ` `    ``{ ` `        ``int` `n = 3, m = 1; ` `        ``Console.WriteLine(numberofways(n, m)); ` `    ``} ` `} ` ` `  `/*This code is contributed by vt_m.*/`

Output:

```3
```