I was trying solving this problem http://codeforces.net/problemset/problem/489/C. Thinkinh in dp manner, I thought i'll need a table that can tell me the number of i digits that sum to particular j. Then if I want to calculate dp[i][j], then my subproblems will be dp[i-1][sum-j] and so on. However, I am unable to implement this idea.
Please help with this. Also, I coded the brute force way: http://ideone.com/83pdfJ but this gives TLE. Where to optimize in it?
Mine code
Yeah, we can do that but I wanted to go for DP manner. Can you please explain that??
I think it would be more difficult to solve this problem with DP.
You can solve it by using string. Submission: 8731134.
It can be solved more easy with greedy algorithm.
Why we are thinking about the leading zeroes? What I thought is for k=1, the only digits are 1 to 9. For k>=0, i'll modify dp[k][j] which denotes k digit with j sum. j<=900 i.e. all possible sum. I'll mark dp[i][1...9] as boolean true or 1. Now, inserting one other for loops which iterate from 0 to 9 (as m) , i'll check if dp[k-1][j-m] is true, if it is, i'll make dp[k][j] as true. Similarly filling whole of the table and then iterating it recursively, I'll get the number. However, this is inefficient complexity wise :P
but i think your approch without considering leading zeroes loos at 100001 because 00001 is false :/
You can use dp approach in a tabular form but only till 4 test cases will be passed but in the 5 test case the number given is 100 digit long which by no way can be stored in the table. Anyways this solution csn be used for dp tabular solution-http://codeforces.net/contest/489/submission/23355950