# Non Decreasing Digits Problem – Dynamic Programming Solutions

«
»

This is a C++ Program that Solves Non Decreasing Digits Problem using Dynamic Programming technique.

Problem Description

A number is said to be made up of non-decreasing digits if all the digits to the left of any digit is less than or equal to that digit.

For example, the four-digit number 1234 is composed of digits that are non-decreasing.

Some other four-digit numbers that are composed of non-decreasing digits are 0011, 1111, 1112, 1122, 2223. As it turns out, there are exactly 715 four-digit numbers composed of non-decreasing digits.

Notice that leading zeroes are required: 0000, 0001, 0002 are all valid four-digit numbers with non-decreasing digits.

For this problem, you will write a program that determines how many such numbers there are with a specified number of digits.

Note: Join free Sanfoundry classes at Telegram or Youtube

Constraints
A decimal integer giving the number of digits N, (1 <= N <= 64)

Problem Solution

In this problem, we create a matrix a[][] where a[i][j]=count of all valid j digit numbers with i as the leading digit. We will fill this matrix row wise, first calculating a then using this value to compute a and so on.

Expected Input and Output

Case-1:

```
number of digits=2
Expected result=55```

Case-2:

Take Data Structure I Mock Tests - Chapterwise!
Start the Test Now: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
```
number of digits=3
Expected result=220```

Case-3:

```
number of digits=4
Expected result=715```
Program/Source Code

Here is source code of the C++ Program to Solve Non Decreasing digits problem. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

1. ` `
2. `//non decreasing digits`
3. `#include<bits/stdc++.h>`
4. `using namespace std;`
5. ` `
6. `int main()`
7. `{`
8. `    int i,j;`
9. `    int n;`
10. ` `
11. `    //number of digits`
12. `    cout<<"Enter the number of digits "<<endl;`
13. `    cin>>n;`
14. ` `
15. `    //matrix to memoize values`
16. `    vector<vector<long long int> > a(10,vector<long long int>(n+1,0));`
17. ` `
18. `    //a[j][i]=count of all possible number with i digits having leading digit j`
19. ` `
20. `    //initialization`
21. `    for(i=0;i<=9;i++)`
22. `        a[i]=1;`
23. ` `
24. `    for(i=1;i<=n;i++)`
25. `        a[i]=1;`
26. ` `
27. `    //for all digits`
28. `    for(i=1;i<=n;i++)`
29. `    {`
30. `        for(j=8;j>=0;j--)`
31. `        {`
32. `            a[j][i]=a[j][i-1]+a[j+1][i];`
33. `        }`
34. `    }`
35. ` `
36. `    //result`
37. `    cout<<"Count of all valid "<<n<<" digit number with non-decreasing digits are "<<endl;`
38. `    cout<<a[n]<<endl;`
39. ` `
40. `    return 0;`
41. `}`
Program Explanation

In the main function, we take the number of digits, n as the input. A matrix is created to store the result of overlapping subproblems. After filling the matrix in a bottom up manner, the result is displayed.

Runtime Test Cases
```
Case-1:
\$ g++ non_decreasing_digits.cpp
\$ ./a.out
Enter the number of digits
2
Count of all valid 2 digit number with non-decreasing digits are
55

Case-2:
\$ ./a.out
Enter the number of digits
3
Count of all valid 3 digit number with non-decreasing digits are
220

Case-3:
\$ ./a.out
Enter the number of digits
4
Count of all valid 4 digit number with non-decreasing digits are
715```

Sanfoundry Global Education & Learning Series – Dynamic Programming Problems.
To practice all Dynamic Programming Problems, here is complete set of 100+ Problems and Solutions. 