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.

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

Expected Input and Output

Case-1:

 
number of digits=2
Expected result=55

Case-2:

Note: Join free Sanfoundry classes at Telegram or Youtube

 
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.

```
 
```
```
//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;
```
```
}
```

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.

« Prev - Cut Ribbon Problem – Dynamic Programming Solutions

» Next - Bytelandian Gold Coins Problem – Dynamic Programming Solutions

Related Posts:

Recommended Articles: