ivplay's blog

By ivplay, 10 years ago, In English


I am stuck on this problem. I can't formulate the recurrence relation exactly. Can anybody help me to formulate the recurrence relation,please? I can think of three state recurrence f(n,k,largest) = how many was we can express n as sum of k distinct integers where none of the integers is greater than largest. If somehow I could compress the last state(largest) by a and k , I could use matrix exponentiation. But how can I eliminate this state?

  • Vote: I like it
  • 0
  • Vote: I do not like it