Digit DP - HELP

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.

1 Like

The time complexity would be order of :

O(N*S)

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

1 Like

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.