Count of all n digit numbers with digits in non-decreasing order
A non-decreasing number is a number whose digits are in non-decreasing order such as 11 12 22 34 33 etc.,
Given a number n which is the length of the number, print the count of all n digit numbers with the digits in non-decreasing order.
For example,
Input: n = 1
Output: count = 10
Explanation: The numbers are 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.
Input: n = 5
Output: count = 2002
Algorithm to find the count of all n-digit numbers with digits in non-decreasing order
One way to investigate the problem is to have the number of numbers equal to the number of n-digit numbers ending with 9 plus the number with the number 8 and the number for 7, and so on.
To get the count with a specific number return for n-1 length and digits less than or equal to the last digit. Below is the recursive formula of the approach,
The above recursive solution contains overlapping subproblems increasing the time complexity.
Therefore, use the Dynamic Programming approach to build a table in a bottom-up manner.