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.