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

给定一个表示位数的整数n>0，则任务是查找本质上不递减的n位正整数的总数。非递减整数是指从左到右的所有数字都是非递减形式的整数。例：12341135。。等注：前导零也是非递减整数，例如0000、0001、0023等，也是4位的非递减整数。 例如：

null

Input : n = 1Output : 10Numbers are 0, 1, 2, ...9.Input : n = 2Output : 55Input : n = 4Output : 715

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

天真的方法： 我们生成所有可能的n位数字，然后针对每个数字检查其是否为非递减。时间复杂度：（n*10^n），其中10^n用于生成所有可能的n位数字，n用于检查特定数字是否为非递减数字。 动态规划： 如果我们从左到右逐个填充数字，以下条件成立。

如果当前的最后一位是9，我们只能在剩余的地方填写9。所以，如果当前的最后一位数字是9，那么只有一种解决方案是可能的。
如果当前最后一位数字小于9，那么我们可以使用以下公式递归计算计数。

a[i][j] = a[i-1][j] + a[i][j + 1]          For every digit j smaller than 9.We consider previous length count and countto be increased by all greater digits.

我们构建一个矩阵a[][]，其中 a[i][j] =以j或大于j为前导数字的所有有效i位非递减整数的计数。解决方案基于以下观察结果。我们按列填充这个矩阵，首先计算a[1][9]，然后使用这个值计算a[2][8]，依此类推。在任何时刻，如果我们想要计算a[i][j]是指前导数字为j或大于j的i位非递减整数的数量，我们应该加上[i-1][j]（i-1位整数的数量，应该从j或更大的数字开始，因为在这种情况下，如果我们把j作为其最左边的数字，那么我们的数字将是i位非递减数字）和[i][j+1]（i位整数的数量，应该从大于j+1的数字开始）。所以 a[i][j]=a[i-1][j]+a[i][j+1] .

图片[1]-n位非递减整数的数目-yiteyi-C++库

C++

                         // C++ program for counting n digit numbers with                       
                         // non decreasing digits                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Returns count of non- decreasing numbers with                       
                         // n digits.                       
                         int                                     nonDecNums(                                     int                                     n)                       
                         {                       
                                                 /* a[i][j] = count of all possible number                       
                                                 with i digits having leading digit as j */                       
                                                 int                                     a[n + 1][10];                       
           
                                                 // Initialization of all 0-digit number                       
                                                 for                                     (                                     int                                     i = 0; i <= 9; i++)                       
                                                 a[0][i] = 1;                       
           
                                                 /* Initialization of all i-digit                       
                                                 non-decreasing number leading with 9*/                       
                                                 for                                     (                                     int                                     i = 1; i <= n; i++)                       
                                                 a[i][9] = 1;                       
           
                                                 /* for all digits we should calculate                       
                                                 number of ways depending upon leading                       
                                                 digits*/                       
                                                 for                                     (                                     int                                     i = 1; i <= n; i++)                       
                                                 for                                     (                                     int                                     j = 8; j >= 0; j--)                       
                                                 a[i][j] = a[i - 1][j] + a[i][j + 1];                       
           
                                                 return                                     a[n][0];                       
                         }                       
           
                         // driver program                       
                         int                                     main()                       
                         {                       
                                                 int                                     n = 2;                       
                                                 cout <<                                     "Non-decreasing digits = "                       
                                                 << nonDecNums(n) << endl;                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program for counting n digit numbers with                       
                         // non decreasing digits                       
                         import                                     java.io.*;                       
           
                         class                                     GFG {                       
           
                                                 // Function that returns count of non- decreasing numbers                       
                                                 // with n digits                       
                                                 static                                     int                                     nonDecNums(                                     int                                     n)                       
                                                 {                       
                                                 // a[i][j] = count of all possible number                       
                                                 // with i digits having leading digit as j                       
                                                 int                                     [][] a =                                     new                                     int                                     [n +                                     1                                     ][                                     10                                     ];                       
           
                                                 // Initialization of all 0-digit number                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i <=                                     9                                     ; i++)                       
                                                 a[                                     0                                     ][i] =                                     1                                     ;                       
           
                                                 // Initialization of all i-digit                       
                                                 // non-decreasing number leading with 9                       
                                                 for                                     (                                     int                                     i =                                     1                                     ; i <= n; i++)                       
                                                 a[i][                                     9                                     ] =                                     1                                     ;                       
           
                                                 // for all digits we should calculate                       
                                                 // number of ways depending upon leading                       
                                                 // digits                       
                                                 for                                     (                                     int                                     i =                                     1                                     ; i <= n; i++)                       
                                                 for                                     (                                     int                                     j =                                     8                                     ; j >=                                     0                                     ; j--)                       
                                                 a[i][j] = a[i -                                     1                                     ][j] + a[i][j +                                     1                                     ];                       
           
                                                 return                                     a[n][                                     0                                     ];                       
                                                 }                       
           
                                                 // driver program                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 int                                     n =                                     2                                     ;                       
                                                 System.out.println(                                     "Non-decreasing digits = "                                     + nonDecNums(n));                       
                                                 }                       
                         }                       
           
                         // Contributed by Pramod Kumar                       

Python3

                         # Python3 program for counting n digit                       
                         # numbers with non decreasing digits                       
                         import                                     numpy as np                       
           
                         # Returns count of non- decreasing                       
                         # numbers with n digits.                       
                         def                                     nonDecNums(n) :                       
                                   
                                                 # a[i][j] = count of all possible number                       
                                                 # with i digits having leading digit as j                       
                                                 a                                     =                                     np.zeros((n                                     +                                     1                                     ,                                     10                                     ))                       
           
                                                 # Initialization of all 0-digit number                       
                                                 for                                     i                                     in                                     range                                     (                                     10                                     ) :                       
                                                 a[                                     0                                     ][i]                                     =                                     1                       
           
                                                 # Initialization of all i-digit                       
                                                 # non-decreasing number leading with 9                       
                                                 for                                     i                                     in                                     range                                     (                                     1                                     , n                                     +                                     1                                     ) :                       
                                                 a[i][                                     9                                     ]                                     =                                     1                       
           
                                                 # for all digits we should calculate                       
                                                 # number of ways depending upon                       
                                                 # leading digits                       
                                                 for                                     i                                     in                                     range                                     (                                     1                                     , n                                     +                                     1                                     ) :                       
                                                 for                                     j                                     in                                     range                                     (                                     8                                     ,                                     -                                     1                                     ,                                     -                                     1                                     ) :                       
                                                 a[i][j]                                     =                                     a[i                                     -                                     1                                     ][j]                                     +                                     a[i][j                                     +                                     1                                     ]                       
           
                                                 return                                     int                                     (a[n][                                     0                                     ])                       
           
                         # Driver Code                       
                         if                                     __name__                                     =                                     =                                     "__main__"                                     :                       
           
                                                 n                                     =                                     2                       
                                                 print                                     (                                     "Non-decreasing digits = "                                     ,                       
                                                 nonDecNums(n))                       
           
                         # This code is contributed by Ryuga                       

C#

                         // C# function to find number of diagonals                       
                         // in n sided convex polygon                       
                         using                                     System;                       
           
                         class                                     GFG {                       
                                   
                                                 // Function that returns count of non-                       
                                                 // decreasing numbers with n digits                       
                                                 static                                     int                                     nonDecNums(                                     int                                     n)                       
                                                 {                       
                                                 // a[i][j] = count of all possible number                       
                                                 // with i digits having leading digit as j                       
                                                 int                                     [, ] a =                                     new                                     int                                     [n + 1, 10];                       
           
                                                 // Initialization of all 0-digit number                       
                                                 for                                     (                                     int                                     i = 0; i <= 9; i++)                       
                                                 a[0, i] = 1;                       
           
                                                 // Initialization of all i-digit                       
                                                 // non-decreasing number leading with 9                       
                                                 for                                     (                                     int                                     i = 1; i <= n; i++)                       
                                                 a[i, 9] = 1;                       
           
                                                 // for all digits we should calculate                       
                                                 // number of ways depending upon leading                       
                                                 // digits                       
                                                 for                                     (                                     int                                     i = 1; i <= n; i++)                       
                                                 for                                     (                                     int                                     j = 8; j >= 0; j--)                       
                                                 a[i, j] = a[i - 1, j] + a[i, j + 1];                       
           
                                                 return                                     a[n, 0];                       
                                                 }                       
           
                                                 // driver program                       
                                                 public                                     static                                     void                                     Main()                       
                                                 {                       
                                                 int                                     n = 2;                       
                                                 Console.WriteLine(                                     "Non-decreasing digits = "                                     +                       
                                                 nonDecNums(n));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Sam007                       

PHP

                         <?php                       
                         // PHP program for counting                       
                         // n digit numbers with                       
                         // non decreasing digits                       
           
                         // Returns count of non-                       
                         // decreasing numbers with                       
                         // n digits.                       
           
                         function                                     nonDecNums(                                     $n                                     )                       
                         {                       
                                                 /* a[i][j] = count of                       
                                                 all possible number                       
                                                 with i digits having                       
                                                 leading digit as j */                       
           
                                                 // Initialization of                       
                                                 // all 0-digit number                       
                                                 for                                     (                                     $i                                     = 0;                                     $i                                     <= 9;                                     $i                                     ++)                       
                                                 $a                                     [0][                                     $i                                     ] = 1;                       
           
                                                 /* Initialization of all                       
                                                 i-digit non-decreasing                       
                                                 number leading with 9*/                       
                                                 for                                     (                                     $i                                     = 1;                                     $i                                     <=                                     $n                                     ;                                     $i                                     ++)                       
                                                 $a                                     [                                     $i                                     ][9] = 1;                       
           
                                                 /* for all digits we should                       
                                                 calculate number of ways                       
                                                 depending upon leading digits*/                       
                                                 for                                     (                                     $i                                     = 1;                                     $i                                     <=                                     $n                                     ;                                     $i                                     ++)                       
                                                 for                                     (                                     $j                                     = 8;                                     $j                                     >= 0;                                     $j                                     --)                       
                                                 $a                                     [                                     $i                                     ][                                     $j                                     ] =                                     $a                                     [                                     $i                                     - 1][                                     $j                                     ] +                       
                                                 $a                                     [                                     $i                                     ][                                     $j                                     + 1];                       
           
                                                 return                                     $a                                     [                                     $n                                     ][0];                       
                         }                       
           
                         // Driver Code                       
                         $n                                     = 2;                       
                         echo                                     "Non-decreasing digits = "                                     ,                       
                                                 nonDecNums(                                     $n                                     ),                                     ""                                     ;                       
           
                         // This code is contributed by m_kit                       
                         ?>                       

Javascript

                         <script>                       
           
                                                 // Javascript program for counting n digit                       
                                                 // numbers with non decreasing digits                       
                                   
                                                 // Function that returns count                       
                                                 // of non- decreasing numbers                       
                                                 // with n digits                       
                                                 function                                     nonDecNums(n)                       
                                                 {                       
                                                 // a[i][j] = count of all possible number                       
                                                 // with i digits having leading digit as j                       
                                                 let a =                                     new                                     Array(n + 1)                       
                                                 for                                     (let i = 0; i < n + 1; i++)                       
                                                 {                       
                                                 a[i] =                                     new                                     Array(10);                       
                                                 }                       
                                   
                                                 // Initialization of all 0-digit number                       
                                                 for                                     (let i = 0; i <= 9; i++)                       
                                                 a[0][i] = 1;                       
                                   
                                                 // Initialization of all i-digit                       
                                                 // non-decreasing number leading with 9                       
                                                 for                                     (let i = 1; i <= n; i++)                       
                                                 a[i][9] = 1;                       
                                   
                                                 // for all digits we should calculate                       
                                                 // number of ways depending upon leading                       
                                                 // digits                       
                                                 for                                     (let i = 1; i <= n; i++)                       
                                                 for                                     (let j = 8; j >= 0; j--)                       
                                                 a[i][j] = a[i - 1][j] + a[i][j + 1];                       
                                   
                                                 return                                     a[n][0];                       
                                                 }                       
                                   
                                                 let n = 2;                       
                                                 document.write(                       
                                                 "Non-decreasing digits = "                                     + nonDecNums(n)                       
                                                 );                       
                                   
                         </script>                       

输出

Non-decreasing digits = 55

输出：

Non-decreasing digits = 55

时间复杂性： O（10*n）相当于O（n）。

另一种方法：

如果我们观察，我们可以看到0必须放在1-9之前，1必须放在2-9之前，依此类推。当我们被要求寻找非递减整数时，111223是一个有效的非递减整数，这意味着相同的数字可以连续出现。

图片[2]-n位非递减整数的数目-yiteyi-C++库

例1 : 当N=2时，我们有11C9，等于 55

例2 ：当N=5时，我们有14C9，等于 2002

C++

                         // CPP program To calculate Number of n-digits non-decreasing integers                       
                         //Contributed by Parishrut Kushwaha//                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Returns factorial of n                       
                         long                                     long                                     int                                     fact(                                     int                                     n)                       
                         {                       
                                                 long                                     long                                     int                                     res = 1;                       
                                                 for                                     (                                     int                                     i = 2; i <= n; i++)                       
                                                 res = res * i;                       
                                                 return                                     res;                       
                         }                       
                                   
                         // returns nCr                       
                         long                                     long                                     int                                     nCr(                                     int                                     n,                                     int                                     r)                       
                         {                       
                                                 return                                     fact(n) / (fact(r) * fact(n - r));                       
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 int                                     n = 2;                       
                                                 cout <<                                     "Number of Non-Decreasing digits: "                                     << nCr(n+9,9);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program To calculate Number                       
                         // of n-digits non-decreasing integers                       
                         class                                     GFG {                       
           
                                                 // Returns factorial of n                       
                                                 static                                     long                                     fact(                                     int                                     n)                       
                                                 {                       
                                                 long                                     res =                                     1                                     ;                       
                                                 for                                     (                                     int                                     i =                                     2                                     ; i <= n; i++)                       
                                                 res = res * i;                       
                                                 return                                     res;                       
                                                 }                       
           
                                                 // returns nCr                       
                                                 static                                     long                                     nCr(                                     int                                     n,                                     int                                     r)                       
                                                 {                       
                                                 return                                     fact(n) / (fact(r) * fact(n - r));                       
                                                 }                       
           
                                                 // Driver code                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 int                                     n =                                     2                                     ;                       
                                                 System.out.println(                       
                                                 "Number of Non-Decreasing digits: "                       
                                                 + nCr(n +                                     9                                     ,                                     9                                     ));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by rajsanghavi9.                       

Python3

                         # Python program To calculate Number of n-digits non-decreasing integers                       
                         #Contributed by Parishrut Kushwaha#                       
                         # Returns factorial of n                       
                         def                                     fact(n):                       
                                   
                                                 res                                     =                                     1                       
                                                 for                                     i                                     in                                     range                                     (                                     2                                     ,n                                     +                                     1                                     ):                       
                                                 res                                     =                                     res                                     *                                     i                       
                                                 return                                     res                       
                                   
                         # returns nCr                       
                         def                                     nCr(n, r):                       
                                                 return                                     fact(n)                                     /                                     /                                     ((fact(r)                                     *                                     fact(n                                     -                                     r)))                       
           
                         # Driver code                       
                         n                                     =                                     2                       
                         print                                     (                                     "Number of Non-Decreasing digits: "                                     , nCr(n                                     +                                     9                                     ,                                     9                                     ))                       
                                   
                         # This code is contributed by shivanisinghss2110                       

C#

                         // C# program To calculate Number                       
                         // of n-digits non-decreasing integers                       
                         using                                     System;                       
           
                         class                                     GFG {                       
           
                                                 // Returns factorial of n                       
                                                 static                                     long                                     fact(                                     int                                     n)                       
                                                 {                       
                                                 long                                     res = 1;                       
                                                 for                                     (                                     int                                     i = 2; i <= n; i++)                       
                                                 res = res * i;                       
                                                 return                                     res;                       
                                                 }                       
           
                                                 // returns nCr                       
                                                 static                                     long                                     nCr(                                     int                                     n,                                     int                                     r)                       
                                                 {                       
                                                 return                                     fact(n) / (fact(r) * fact(n - r));                       
                                                 }                       
           
                                                 // Driver code                       
                                                 public                                     static                                     void                                     Main(String[] args)                       
                                                 {                       
                                                 int                                     n = 2;                       
                                                 Console.Write(                                     "Number of Non-Decreasing digits: "                                     + nCr(n + 9, 9));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by shivanisinghss2110                       

Javascript

                         <script>                       
                         // JavaScript program To calculate Number                       
                         // of n-digits non-decreasing integers                       
           
                                                 // Returns factorial of n                       
                                                 function                                     fact( n)                       
                                                 {                       
                                                 var                                     res = 1;                       
                                                 for                                     (                                     var                                     i = 2; i <= n; i++)                       
                                                 res = res * i;                       
                                                 return                                     res;                       
                                                 }                       
           
                                                 // returns nCr                       
                                                 function                                     nCr(n, r)                       
                                                 {                       
                                                 return                                     fact(n) / (fact(r) * fact(n - r));                       
                                                 }                       
           
                                                 // Driver code                       
                                                 var                                     n = 2;                       
                                                 document.write(                                     "Number of Non-Decreasing digits: "                                     + nCr(n + 9, 9));                       
           
                         // This code is contributed by shivanisinghss2110.                       
           
                         </script>                       

输出

Number of Non-Decreasing digits: 55

时间复杂性： O（n）。

空间复杂性： O（n）。本文由 希瓦姆·普拉丹（anuj_charm） .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用贡献极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

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

THE END

技术文章