# Total number of non-decreasing numbers with n digits using dynamic programming

Given the number of digits **n**, find the count of total non-decreasing numbers with *n* digits.

A number is non-decreasing if every digit (except the first one) is greater than or equal to the previous digit. For example, 22,223, 45567, 899, are non-decreasing numbers whereas 321 or 322 are not.

**Input:**

The first line of input contains an integer **T** denoting the number of test cases. Then **T** test cases follow. The first line of each test case contains the integer **n**.

**Output:**

Print the count of total non-decreasing numbers with n digits for each test case in a new line. You may need to use unsigned long long int as the count can be very large.

**Constraints:**

1 <= T <= 100
1 <= n <= 200

**Example:**

Input:
No of test cases, 3
n=1
n=2
n=3
Output:
For n=1
Total count is: 10
For n=2
Total count is: 55
For n=3
Total count is: 220

**Explanation:**

For n=1,
The non-decreasing numbers are basically 0 to 9,
counting up to 10
For, n=2,
The non-decreasing numbers can be
00
01
02
..
11
12
13
14
15
.. so on total 55

The solution can be recursive. In recursion our strategy will be to build the string (read: number) such that at each recursive call the number to be appended would be necessarily bigger (or equal) than(to) the last one.

Say, at any recursion call,

The number already constructed is

x1x2...xiwherei<n, So at the recursive call we are allowed to append digits only which are equal to greater toxi.So, let's formulate the recursion

Say, the recursive function is

computerecur(int index, int last, int n)Where,

index= current position to append digitLast= the previous digitn= number of total digitsSo the basic idea to the recursion is that if it's a valid digit to append (depending on the last digit) then append it and recur for the remaining digits.

Now the call from the

main()function should be done by appending the first digit already (basically we will keep that first digit as last digit position for the recursion call).So at main,

We will call as,

The result is the ultimate result.

I would suggest you draw the recursion tree to have a better understanding, Take

n=3and do yourself.For,

n=2, I will brief the tree belowNow, it's pretty easy to infer that it leads to many overlapping sub-problem and hence we need dynamic programming to store the results of overlapping sub-problems. That's why I have used the memoization technique to store the already computed sub-problem results. See the below implementation to understand the memorization part.

C++ Implementation:

need an explanation for this answer? contact us directly to get an explanation for this answerOutput: