A non-decreasing number has every digit greater than or equal to the previous digit. Given the number of digits, find how many numbers exist with non-decreasing digits.
Input: int digits = 3; Output: 220 Explanation: There are 220 numbers with 3 digits that have non-decreasing digits: …, 111, 112, …, 222, 223, 224, …. |
Solution:
1. static int countNonDecreasing(int digits) { 2. int[][] nonDecreasingNumbers = new int[10][digits + 1]; 3. 4. for (int i = 0; i < 10; i++) { 5. nonDecreasingNumbers[i][1] = 1; 6. } 7. 8. for (int digit = 0; digit <= 9; digit++) { 9. for (int length = 2; length <= digits; length++) { 10. for (int lastDigit = 0; lastDigit <= digit; lastDigit++) { 11. nonDecreasingNumbers[digit][length] += nonDecreasingNumbers[lastDigit][length - 1]; 12. } 13. } 14. } 15. 16. int count = 0; 17. for (int i = 0; i < 10; i++) { 18. count += nonDecreasingNumbers[i][digits]; 19. } 20. return count; 21. } 22.