jugal_sahu's blog

COUNT — Another Very Easy Problem! WOW!!! SPOJ
By jugal_sahu, 10 years ago, In English

I was trying to solve COUNT(spoj problem).I am able to solve it using 3D DP but it will give segmentation fault because of the constraints.Can anyone help?

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Always post the link to the problem when you ask for help.

Solution:

dp[n][k] -- the answer.

One can fix the number of ones in final partition:

0 ones -- dp[n - k][k] ways,

1 one -- dp[n - k][k - 1] ways,

...

n ones -- dp[n - k][0] ways.

So dp[n][k] = .

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How is it different from P(n,k), partitioning ‘n’ elements in ‘k’ sets?

→ Reply