n位数的非降序总数

当所有数字（首位除外）均不小于其前一个数字时，该数字被称为不递减。对于此算法，我们必须找出N位数字中有多少个非递减数字。

让count(n,d)函数计算长度为n并以字母d结尾的不减数字的数量，然后我们可以这样写关系。

$$count(n,d)= \ displaystyle \ sum \ limits_ {i = 0} ^ d count(n-1,i)\\ total = \ displaystyle \ sum \ limits_ {d = 0} ^ {n-1 } count(n-1,d)$$

输入输出

Input:
Number of digits, say 3.
Output:
The possible non decreasing numbers. Here it is 220.
Non decreasing numbers are like 111, 112, 123, 789, 569 etc.

算法

countNumbers(n)

输入： 给定值。

输出：  n位数字中非递减值的数量。

Begin
   define count matrix of order (10 x n+1), and fill with 0
   for i := 0 to 9, do
      count[i, 1] := 1
   done

   for digit := 0 to 9, do
      for len := 2 to n, do
         for x := 0 to digit, do
            count[digit, len] := count[digit, len] + count[x, len-1]
         done
      done
   done

   nonDecNum := 0
   for i := 0 to 9, do
      nonDecNum := nonDecNum + count[i, n]
   done

   return nonDecNum
End

示例

#include<iostream>
using namespace std;

long long int countNumbers(int n) {
   long long int count[10][n+1];    //to store total non decreasing number starting with i digit and length j

   for(int i = 0; i<10; i++)
      for(int j = 0; j<n+1; j++)
         count[i][j] = 0;     //initially set all elements to 0

   for (int i = 0; i < 10; i++)    //set non decreasing numbers of 1 digit
      count[i][1] = 1;

   for (int digit = 0; digit <= 9; digit++) {     //for all digits 0-9
      for (int len = 2; len <= n; len++) {       //for those numbers (length 2 to n)
         for (int x = 0; x <= digit; x++)
            count[digit][len] += count[x][len-1];     //last digit x <= digit, add with number of len-1
      }
   }

   long long int nonDecNum = 0;

   for (int i = 0; i < 10; i++)    //total non decreasing numbers starting with 0-9
      nonDecNum += count[i][n];
   return nonDecNum;
}

int main() {
   int n = 3;
   cout << "Enter number of digits: "; cin >> n;
   cout << "Total non decreasing numbers: " << countNumbers(n);
}

输出结果

Enter number of digits: 3
Total non decreasing numbers: 220