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

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.

Constraints

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

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[9][1] then using this value to compute a[8][2] and so on.

Case-1:

number of digits=2 Expected result=55

Case-2:

number of digits=3 Expected result=220

Case-3:

number of digits=4 Expected result=715

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.

`//non decreasing digits`

`#include<bits/stdc++.h>`

using namespace std;

int main()

`{`

int i,j;

int n;

`//number of digits`

cout<<"Enter the number of digits "<<endl;

cin>>n;

`//matrix to memoize values`

vector<vector<long long int> > a(10,vector<long long int>(n+1,0));

`//a[j][i]=count of all possible number with i digits having leading digit j`

`//initialization`

for(i=0;i<=9;i++)

a[i][0]=1;

for(i=1;i<=n;i++)

a[9][i]=1;

`//for all digits`

for(i=1;i<=n;i++)

`{`

for(j=8;j>=0;j--)

`{`

a[j][i]=a[j][i-1]+a[j+1][i];

`}`

`}`

`//result`

cout<<"Count of all valid "<<n<<" digit number with non-decreasing digits are "<<endl;

cout<<a[0][n]<<endl;

return 0;

`}`

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.

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__.