How to solve this problem using DP.

**FIND THE COUNT OF ALL THE NUMBERS HAVING LENGTH N AND SUM OF DIGITS S**

What are the constraints?

**First lets look at the more general problem:**

**Ques:** Given N variables which sum upto S find number of ways where N variables can take any value from 0 to 9 inclusive:

## Solution

`Let us take dp[n][S] representing the number of ways we can write sum S as sum of n variables. Therefore we can see that dp[n][s]= dp[n-1][s]+dp[n-1][s-1]....+dp[n-1][s-9].`

Now the above problem can be converted to this where we have n variables and the first variable can be from 1 to 9 and others can be from 0 to 9.

## Hint

`Our final ans would be dp[n-1][s-1]+dp[n-1][s-2]+...dp[n-1][s-9] and dp[n-1][x] we can write normally as from the former expression since its value can be from 0 to 9.`

**The time complexity would be order of :**

O(N*S)

where N is the length of the Number and S is the desired Sum.

N <=18 ,

Okk then , the guy above has mentioned the solution , hoping that this problem is not from ongoing contest

Not at all , i was just solving a problem on codeforces for finding the largest and smallest number with sum s and length n , i have just extended the idea of the question.