I thought that this problem is so easy. After many tries to solve that I should say: that is not so easy and I cant solve it! Please, if you DP-master tell me where I'm wrong.

So, the state is dp[sum][length] += dp[sum - digit][length - 1], for each digit 0..9. The base is dp[1..9][1] = 1.

I've got WA#10:
My program for 10 output: 43756 (correct answer: 43749)

I can't find a little bug ;(

[code]

    for s := 1; s <= S; s++ {
        for l := 2; l <= 9; l++ {
            for d := 0; d < 10 && s - d > 0; d++ {
                if dp[s - d][l - 1] == 0 {
                    continue
                }

                dp[s][l] += dp[s - d][l - 1]

                if d == 0 {
                    dp[s][l]++
                }
            }
        }
    }
[/code]

Please anyone...

You don't need to store previous positions:

for (int position = 2; position <= 9; position++)
  for (int sum = 81; sum > 0; sum--)
    for (int digit = 1; digit <= 9; digit++) if (sum >= digit)
      ways[sum] += ways[sum - digit];

because you have to start l at one and eliminate continue and s - d >= 0

Here is the solution
http://xoptutorials.com/index.php/2017/01/01/timus1353/

Guys, what are you doing in New Year? Hahaha

No. You are wrong here.
I've found my error, it was a dp base.

Thx for all.