A number is non-decreasing if each of its digits is greater than or equal to the previous digit. For example, 223, 4455567, 899, are non-decreasing numbers. 
Given an integer N, find the total number of non-decreasing numbers that have N digits.
Example 1:
Input: N = 1
Output: 10
Explaination: All the single digit numbers 
are non-decreasing. So count is 10.
Example 2:
Input: N = 2
Output: 55
Explaination: For number starting with 1 there 
is 1 decreasing number 10, for number starting 
with 2 there are 2 decreasing numbers. 
Similarly numbers starting with 3, 4 . . . 9 
there are 3, 4 . . . 9 decreasing numbers. 
Total 45 decreasing numbers. Total possible 
numbers are 10^{2} = 100. So total number of 
non-decreasing numbers are 100-45 = 55.
Your Task:
You do not need to read input or print anything. Your task is to complete the function count() which takes the number N as input parameter and return the total number of non-decreasing numbers.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 500

Source: geeksforgeeks | Difficulty: EASY
Tags: Dynamic programming

Starter code: #User function Template for python3



class Solution:

    def count(self, N):

        # code here

Solutions:
class Solution:

	def count(self, N):
		dp = [[0] * 10 for i in range(N)]
		for i in range(10):
			dp[0][i] = 1
			if i != 0:
				dp[0][i] += dp[0][i - 1]
		for i in range(1, N):
			for j in range(10):
				dp[i][j] = dp[i - 1][j]
				if j != 0:
					dp[i][j] += dp[i][j - 1]
		return dp[N - 1][9]


class Solution:

	def count(self, n):
		dp = [[0 for _ in range(10)] for __ in range(n + 1)]
		for i in range(10):
			dp[1][i] = 1
		for l in range(2, n + 1):
			for digit in range(10):
				for x in range(digit + 1):
					dp[l][digit] += dp[l - 1][x]
		count = 0
		for i in range(10):
			count += dp[n][i]
		return count