n位非递减数的总数-yiteyi-C++库

如果每个数字（第一个数字除外）大于或等于前一个数字，则该数字是非递减的。例如，22344567899是非递减数字。所以，给定n位数，你需要找到n位数的非递减总数。 例如：

null

Input:  n = 1Output: count  = 10Input:  n = 2Output: count  = 55Input:  n = 3Output: count  = 220

我们强烈建议您尽量减少浏览器，并先自己尝试。 看待这个问题的一种方法是，数的计数等于n个以9结尾的数字加上以8结尾的数字加上7的计数，以此类推。如何获得以特定数字结尾的计数？我们可以重复n-1长度和小于或等于最后一个数字的数字。下面是递归公式。

Count of n digit numbers = (Count of (n-1) digit numbers Ending with digit 9) +                           (Count of (n-1) digit numbers Ending with digit 8) +                           .............................................+                            .............................................+                           (Count of (n-1) digit numbers Ending with digit 0)

让count以数字“d”结尾，长度n为count（n，d）

count(n, d) = ∑(count(n-1, i)) where i varies from 0 to dTotal count = ∑count(n-1, d) where d varies from 0 to n-1

上面的递归解将有许多重叠的子问题。因此，我们可以使用动态规划以自下而上的方式构建一个表。以下是上述理念的实施：

C++

                         // C++ program to count non-decreasing number with n digits                       
                         #include<bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         long                                     long                                     int                                     countNonDecreasing(                                     int                                     n)                       
                         {                       
                                                 // dp[i][j] contains total count of non decreasing                       
                                                 // numbers ending with digit i and of length j                       
                                                 long                                     long                                     int                                     dp[10][n+1];                       
                                                 memset                                     (dp, 0,                                     sizeof                                     dp);                       
           
                                                 // Fill table for non decreasing numbers of length 1                       
                                                 // Base cases 0, 1, 2, 3, 4, 5, 6, 7, 8, 9                       
                                                 for                                     (                                     int                                     i = 0; i < 10; i++)                       
                                                 dp[i][1] = 1;                       
           
                                                 // Fill the table in bottom-up manner                       
                                                 for                                     (                                     int                                     digit = 0; digit <= 9; digit++)                       
                                                 {                       
                                                 // Compute total numbers of non decreasing                       
                                                 // numbers of length 'len'                       
                                                 for                                     (                                     int                                     len = 2; len <= n; len++)                       
                                                 {                       
                                                 // sum of all numbers of length of len-1                       
                                                 // in which last digit x is <= 'digit'                       
                                                 for                                     (                                     int                                     x = 0; x <= digit; x++)                       
                                                 dp[digit][len] += dp[x][len-1];                       
                                                 }                       
                                                 }                       
           
                                                 long                                     long                                     int                                     count = 0;                       
           
                                                 // There total nondecreasing numbers of length n                       
                                                 // won't be dp[0][n] +  dp[1][n] ..+ dp[9][n]                       
                                                 for                                     (                                     int                                     i = 0; i < 10; i++)                       
                                                 count += dp[i][n];                       
           
                                                 return                                     count;                       
                         }                       
           
                         // Driver program                       
                         int                                     main()                       
                         {                       
                                                 int                                     n = 3;                       
                                                 cout << countNonDecreasing(n);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         class                                     NDN                       
                         {                       
                                                 static                                     int                                     countNonDecreasing(                                     int                                     n)                       
                                                 {                       
                                                 // dp[i][j] contains total count of non decreasing                       
                                                 // numbers ending with digit i and of length j                       
                                                 int                                     dp[][] =                                     new                                     int                                     [                                     10                                     ][n+                                     1                                     ];                       
                                   
                                                 // Fill table for non decreasing numbers of length 1                       
                                                 // Base cases 0, 1, 2, 3, 4, 5, 6, 7, 8, 9                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i <                                     10                                     ; i++)                       
                                                 dp[i][                                     1                                     ] =                                     1                                     ;                       
                                   
                                                 // Fill the table in bottom-up manner                       
                                                 for                                     (                                     int                                     digit =                                     0                                     ; digit <=                                     9                                     ; digit++)                       
                                                 {                       
                                                 // Compute total numbers of non decreasing                       
                                                 // numbers of length 'len'                       
                                                 for                                     (                                     int                                     len =                                     2                                     ; len <= n; len++)                       
                                                 {                       
                                                 // sum of all numbers of length of len-1                       
                                                 // in which last digit x is <= 'digit'                       
                                                 for                                     (                                     int                                     x =                                     0                                     ; x <= digit; x++)                       
                                                 dp[digit][len] += dp[x][len-                                     1                                     ];                       
                                                 }                       
                                                 }                       
                                   
                                                 int                                     count =                                     0                                     ;                       
                                   
                                                 // There total nondecreasing numbers of length n                       
                                                 // won't be dp[0][n] +  dp[1][n] ..+ dp[9][n]                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i <                                     10                                     ; i++)                       
                                                 count += dp[i][n];                       
                                   
                                                 return                                     count;                       
                                                 }                       
                                                 public                                     static                                     void                                     main(String args[])                       
                                                 {                       
                                                 int                                     n =                                     3                                     ;                       
                                                 System.out.println(countNonDecreasing(n));                       
                                                 }                       
                         }                                     /* This code is contributed by Rajat Mishra */                       

Python3

                         # Python3 program to count                       
                         # non-decreasing number with n digits                       
                         def                                     countNonDecreasing(n):                       
                                   
                                                 # dp[i][j] contains total count                       
                                                 # of non decreasing numbers ending                       
                                                 # with digit i and of length j                       
                                                 dp                                     =                                     [[                                     0                                     for                                     i                                     in                                     range                                     (n                                     +                                     1                                     )]                       
                                                 for                                     i                                     in                                     range                                     (                                     10                                     )]                       
                                   
                                                 # Fill table for non decreasing                       
                                                 # numbers of length 1.                       
                                                 # Base cases 0, 1, 2, 3, 4, 5, 6, 7, 8, 9                       
           
                                                 for                                     i                                     in                                     range                                     (                                     10                                     ):                       
                                                 dp[i][                                     1                                     ]                                     =                                     1                       
           
                                                 # Fill the table in bottom-up manner                       
                                                 for                                     digit                                     in                                     range                                     (                                     10                                     ):                       
                                   
                                                 # Compute total numbers of non                       
                                                 # decreasing numbers of length 'len'                       
                                                 for                                     len                                     in                                     range                                     (                                     2                                     , n                                     +                                     1                                     ):                       
                                   
                                                 # sum of all numbers of length                       
                                                 # of len-1 in which last                       
                                                 # digit x is <= 'digit'                       
                                                 for                                     x                                     in                                     range                                     (digit                                     +                                     1                                     ):                       
                                                 dp[digit][                                     len                                     ]                                     +                                     =                                     dp[x][                                     len                                     -                                     1                                     ]                       
                                                 count                                     =                                     0                       
                                   
                                                 # There total nondecreasing numbers                       
                                                 # of length n won't be dp[0][n] +                       
                                                 # dp[1][n] ..+ dp[9][n]                       
                                                 for                                     i                                     in                                     range                                     (                                     10                                     ):                       
                                                 count                                     +                                     =                                     dp[i][n]                       
                                                 return                                     count                       
                                   
                         # Driver Code                       
                         n                                     =                                     3                       
                         print                                     (countNonDecreasing(n))                       
           
                         # This code is contributed                       
                         # by sahilshelangia                       

C#

                         // C# program to print sum                       
                         // triangle for a given array                       
                         using                                     System;                       
           
                         class                                     GFG {                       
                                   
                                                 static                                     int                                     countNonDecreasing(                                     int                                     n)                       
                                                 {                       
                                                 // dp[i][j] contains total count                       
                                                 // of non decreasing numbers ending                       
                                                 // with digit i and of length j                       
                                                 int                                     [,]dp =                                     new                                     int                                     [10,n + 1];                       
                                   
                                                 // Fill table for non decreasing                       
                                                 // numbers of length 1 Base cases                       
                                                 // 0, 1, 2, 3, 4, 5, 6, 7, 8, 9                       
                                                 for                                     (                                     int                                     i = 0; i < 10; i++)                       
                                                 dp[i, 1] = 1;                       
                                   
                                                 // Fill the table in bottom-up manner                       
                                                 for                                     (                                     int                                     digit = 0; digit <= 9; digit++)                       
                                                 {                       
                                   
                                                 // Compute total numbers of non decreasing                       
                                                 // numbers of length 'len'                       
                                                 for                                     (                                     int                                     len = 2; len <= n; len++)                       
                                                 {                       
                                   
                                                 // sum of all numbers of length of len-1                       
                                                 // in which last digit x is <= 'digit'                       
                                                 for                                     (                                     int                                     x = 0; x <= digit; x++)                       
                                                 dp[digit, len] += dp[x, len - 1];                       
                                                 }                       
                                                 }                       
                                   
                                                 int                                     count = 0;                       
                                   
                                                 // There total nondecreasing numbers                       
                                                 // of length n won't be dp[0][n]                       
                                                 // + dp[1][n] ..+ dp[9][n]                       
                                                 for                                     (                                     int                                     i = 0; i < 10; i++)                       
                                                 count += dp[i, n];                       
                                   
                                                 return                                     count;                       
                                                 }                       
                                   
                                                 // Driver code                       
                                                 public                                     static                                     void                                     Main()                       
                                                 {                       
                                                 int                                     n = 3;                       
                                                 Console.WriteLine(countNonDecreasing(n));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Sam007.                       

PHP

                         <?php                       
           
                         // PHP program to count non-decreasing number with n digits                       
                                   
                         function                                     countNonDecreasing(                                     $n                                     )                       
                         {                       
                                                 // dp[i][j] contains total count of non decreasing                       
                                                 // numbers ending with digit i and of length j                       
                                                 $dp                                     =                                     array_fill                                     (0,10,                                     array_fill                                     (0,                                     $n                                     +1,NULL));                       
                                   
                                                 // Fill table for non decreasing numbers of length 1                       
                                                 // Base cases 0, 1, 2, 3, 4, 5, 6, 7, 8, 9                       
                                                 for                                     (                                     $i                                     = 0;                                     $i                                     < 10;                                     $i                                     ++)                       
                                                 $dp                                     [                                     $i                                     ][1] = 1;                       
                                   
                                                 // Fill the table in bottom-up manner                       
                                                 for                                     (                                     $digit                                     = 0;                                     $digit                                     <= 9;                                     $digit                                     ++)                       
                                                 {                       
                                                 // Compute total numbers of non decreasing                       
                                                 // numbers of length 'len'                       
                                                 for                                     (                                     $len                                     = 2;                                     $len                                     <=                                     $n                                     ;                                     $len                                     ++)                       
                                                 {                       
                                                 // sum of all numbers of length of len-1                       
                                                 // in which last digit x is <= 'digit'                       
                                                 for                                     (                                     $x                                     = 0;                                     $x                                     <=                                     $digit                                     ;                                     $x                                     ++)                       
                                                 $dp                                     [                                     $digit                                     ][                                     $len                                     ] +=                                     $dp                                     [                                     $x                                     ][                                     $len                                     -1];                       
                                                 }                       
                                                 }                       
                                   
                                                 $count                                     = 0;                       
                                   
                                                 // There total nondecreasing numbers of length n                       
                                                 // won't be dp[0][n] +  dp[1][n] ..+ dp[9][n]                       
                                                 for                                     (                                     $i                                     = 0;                                     $i                                     < 10;                                     $i                                     ++)                       
                                                 $count                                     +=                                     $dp                                     [                                     $i                                     ][                                     $n                                     ];                       
                                   
                                                 return                                     $count                                     ;                       
                         }                       
                                   
                         // Driver program                       
           
                         $n                                     = 3;                       
                         echo                                     countNonDecreasing(                                     $n                                     );                       
                         return                                     0;                       
                         ?>                       

Javascript

                         <script>                       
                                   
                                                 function                                     countNonDecreasing(n)                       
                                                 {                       
                                                 // dp[i][j] contains total count of non decreasing                       
                                                 // numbers ending with digit i and of length j                       
                                                 let dp=                                     new                                     Array(10);                       
                                                 for                                     (let i=0;i<10;i++)                       
                                                 {                       
                                                 dp[i]=                                     new                                     Array(n+1);                       
                                                 }                       
                                   
                                   
                                                 for                                     (let i=0;i<10;i++)                       
                                                 {                       
                                                 for                                     (let j=0;j<n+1;j++)                       
                                                 {                       
                                                 dp[i][j]=0;                       
                                                 }                       
                                                 }                       
                                   
                                                 // Fill table for non decreasing numbers of length 1                       
                                                 // Base cases 0, 1, 2, 3, 4, 5, 6, 7, 8, 9                       
                                                 for                                     (let i = 0; i < 10; i++)                       
                                                 dp[i][1] = 1;                       
                                   
                                                 // Fill the table in bottom-up manner                       
                                                 for                                     (let digit = 0; digit <= 9; digit++)                       
                                                 {                       
                                                 // Compute total numbers of non decreasing                       
                                                 // numbers of length 'len'                       
                                                 for                                     (let len = 2; len <= n; len++)                       
                                                 {                       
                                                 // sum of all numbers of length of len-1                       
                                                 // in which last digit x is <= 'digit'                       
                                                 for                                     (let x = 0; x <= digit; x++)                       
                                                 dp[digit][len] += dp[x][len-1];                       
                                                 }                       
                                                 }                       
                                   
                                                 let count = 0;                       
                                   
                                                 // There total nondecreasing numbers of length n                       
                                                 // won't be dp[0][n] +  dp[1][n] ..+ dp[9][n]                       
                                                 for                                     (let i = 0; i < 10; i++)                       
                                                 count += dp[i][n];                       
                                   
                                                 return                                     count;                       
                                                 }                       
                                   
                                                 let n = 3;                       
                                                 document.write(countNonDecreasing(n));                       
                                   
                                                 // This code is contributed by avanitrachhadiya2155                       
           
                         </script>                       

输出：

幸亏高拉夫·阿希瓦感谢您提出上述方法。 另一种方法是基于下面的直接公式

Count of non-decreasing numbers with n digits =                                 N*(N+1)/2*(N+2)/3* ....*(N+n-1)/nWhere N = 10

下面是使用上述公式计算计数的程序。

C++

                         // C++ program to count non-decreasing number with n digits                       
                         #include<bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         long                                     long                                     int                                     countNonDecreasing(                                     int                                     n)                       
                         {                       
                                                 int                                     N = 10;                       
           
                                                 // Compute value of N*(N+1)/2*(N+2)/3* ....*(N+n-1)/n                       
                                                 long                                     long                                     count = 1;                       
                                                 for                                     (                                     int                                     i=1; i<=n; i++)                       
                                                 {                       
                                                 count *= (N+i-1);                       
                                                 count /= i;                       
                                                 }                       
           
                                                 return                                     count;                       
                         }                       
           
                         // Driver program                       
                         int                                     main()                       
                         {                       
                                                 int                                     n = 3;                       
                                                 cout << countNonDecreasing(n);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // java program to count non-decreasing                       
                         // number with n digits                       
                         public                                     class                                     GFG {                       
                                   
                                                 static                                     long                                     countNonDecreasing(                                     int                                     n)                       
                                                 {                       
                                                 int                                     N =                                     10                                     ;                       
                                   
                                                 // Compute value of N * (N+1)/2 *                       
                                                 // (N+2)/3 * ....* (N+n-1)/n                       
                                                 long                                     count =                                     1                                     ;                       
                                   
                                                 for                                     (                                     int                                     i =                                     1                                     ; i <= n; i++)                       
                                                 {                       
                                                 count *= (N + i -                                     1                                     );                       
                                                 count /= i;                       
                                                 }                       
                                   
                                                 return                                     count;                       
                                                 }                       
           
                                                 // Driver code                       
                                                 public                                     static                                     void                                     main(String args[]) {                       
                                   
                                                 int                                     n =                                     3                                     ;                       
                                                 System.out.print(countNonDecreasing(n));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Sam007.                       

Python3

                         # python program to count non-decreasing                       
                         # number with n digits                       
           
                         def                                     countNonDecreasing(n):                       
                                                 N                                     =                                     10                       
           
                                                 # Compute value of N*(N+1)/2*(N+2)/3                       
                                                 # * ....*(N+n-1)/n                       
                                                 count                                     =                                     1                       
                                                 for                                     i                                     in                                     range                                     (                                     1                                     , n                                     +                                     1                                     ):                       
                                                 count                                     =                                     int                                     (count                                     *                                     (N                                     +                                     i                                     -                                     1                                     ))                       
                                                 count                                     =                                     int                                     (count                                     /                                     i )                       
                                   
                                                 return                                     count                       
           
                         # Driver program                       
                         n                                     =                                     3                                     ;                       
                         print                                     (countNonDecreasing(n))                       
                                   
                         # This code is contributed by Sam007                       

C#

                         // C# program to count non-decreasing                       
                         // number with n digits                       
                         using                                     System;                       
           
                         class                                     GFG {                       
                                   
                                                 static                                     long                                     countNonDecreasing(                                     int                                     n)                       
                                                 {                       
                                                 int                                     N = 10;                       
                                   
                                                 // Compute value of N * (N+1)/2 *                       
                                                 // (N+2)/3 * ....* (N+n-1)/n                       
                                                 long                                     count = 1;                       
                                   
                                                 for                                     (                                     int                                     i = 1; i <= n; i++)                       
                                                 {                       
                                                 count *= (N + i - 1);                       
                                                 count /= i;                       
                                                 }                       
                                   
                                                 return                                     count;                       
                                                 }                       
           
                                   
                                                 public                                     static                                     void                                     Main()                       
                                                 {                       
                                                 int                                     n = 3;                       
                                   
                                                 Console.WriteLine(countNonDecreasing(n));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Sam007.                       

PHP

                         <?php                       
                         // PHP program to count non-decreasing                       
                         // number with n digits                       
           
                         function                                     countNonDecreasing(                                     $n                                     )                       
                         {                       
                                                 $N                                     = 10;                       
           
                                                 // Compute value of N*(N+1)/2*(N+2)/3* ...                       
                                                 // ....*(N+n-1)/n                       
                                                 $count                                     = 1;                       
                                                 for                                     (                                     $i                                     = 1;                                     $i                                     <=                                     $n                                     ;                                     $i                                     ++)                       
                                                 {                       
                                                 $count                                     *= (                                     $N                                     +                                     $i                                     - 1);                       
                                                 $count                                     /=                                     $i                                     ;                       
                                                 }                       
           
                                                 return                                     $count                                     ;                       
                         }                       
           
                                                 // Driver Code                       
                                                 $n                                     = 3;                       
                                                 echo                                     countNonDecreasing(                                     $n                                     );                       
                                   
                         // This code is contributed by Sam007                       
                         ?>                       

Javascript

                         <script>                       
           
                         // javascript program to count non-decreasing                       
                         // number with n digits                       
                                   
                                                 function                                     countNonDecreasing(n)                       
                                                 {                       
                                                 let N = 10;                       
                                   
                                                 // Compute value of N * (N+1)/2 *                       
                                                 // (N+2)/3 * ....* (N+n-1)/n                       
                                                 let count = 1;                       
                                   
                                                 for                                     (let i = 1; i <= n; i++)                       
                                                 {                       
                                                 count *= (N + i - 1);                       
                                                 count = Math.floor(count/ i);                       
                                                 }                       
                                   
                                                 return                                     count;                       
                                                 }                       
                                   
                                                 // Driver code                       
                                                 let n = 3;                       
                                                 document.write(countNonDecreasing(n));                       
                                   
                                                 //  This code is contributed by rag2127.                       
                         </script>                       

输出：

幸亏阿披舍克·索马尼感谢你提出这种方法。 这个公式是如何工作的？

N * (N+1)/2 * (N+2)/3 * .... * (N+n-1)/nWhere N = 10

让我们尝试不同的n值。

For n = 1, the value is N from formula.Which is true as for n = 1, we have all single digitnumbers, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.For n = 2, the value is N(N+1)/2 from formulaWe can have N numbers beginning with 0, (N-1) numbers beginning with 1, and so on.So sum is N + (N-1) + .... + 1 = N(N+1)/2For n = 3, the value is N(N+1)/2(N+2)/3 from formulaWe can have N(N+1)/2 numbers beginning with 0, (N-1)N/2 numbers beginning with 1 (Note that when we begin with 1, we have N-1 digits left to consider for remaining places),(N-2)(N-1)/2 beginning with 2, and so on.Count = N(N+1)/2 + (N-1)N/2 + (N-2)(N-1)/2 +                                (N-3)(N-2)/2 .... 3 + 1      [Combining first 2 terms, next 2 terms and so on]     = 1/2[N² + (N-2)² + .... 4]     = N*(N+1)*(N+2)/6  [Refer this , putting n=N/2 in the                          even sum formula]

对于一般n位数的情况，我们可以应用数学归纳法。计数将等于以0开头的n-1个数字的计数，即n*（n+1）/2*（n+2）/3**（N+N-1-1）/（N-1）。加上以1开头的n-1位数的计数，即（n-1）*（n）/2*（n+1）/3**（N-1+N-1-1）/（N-1）（注意N被N-1替换）等等。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章