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.
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 then using this value to compute a and so on.
number of digits=2 Expected result=55
number of digits=3 Expected result=220
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
using namespace std;
//number of digits
cout<<"Enter the number of digits "<<endl;
//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
//for all digits
cout<<"Count of all valid "<<n<<" digit number with non-decreasing digits are "<<endl;
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.