Why this DP solution doesnt work?

Posted by

Dmitriy 11 Oct 2016 14:17

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 ;(

Re: Why this DP solution doesnt work?

Posted by

Dmitriy 11 Oct 2016 14:18

[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]

Re: Why this DP solution doesnt work?

Posted by

Dmitriy 16 Oct 2016 09:20

Please anyone...

Re: Why this DP solution doesnt work?

Posted by

Egor 1 Dec 2016 23:39

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];

Re: Why this DP solution doesnt work?

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

Re: Why this DP solution doesnt work?

Re: Why this DP solution doesnt work?

Guys, what are you doing in New Year? Hahaha

Re: Why this DP solution doesnt work?

Posted by

Dmitriy 13 Feb 2018 06:22

No. You are wrong here.

I've found my error, it was a dp base.

Thx for all.