ialwaysusethisaccount's blog

how to do project euler 76 with DP
By ialwaysusethisaccount, 9 years ago, In English

It is possible to write five as a sum in exactly six different ways:

4 + 1 3 + 2 3 + 1 + 1 2 + 2 + 1 2 + 1 + 1 + 1 1 + 1 + 1 + 1 + 1

How many different ways can one hundred be written as a sum of at least two positive integers?

i am looking for a top-down recursive solution. thanx.

  • Vote: I like it
  • -2
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For example answer is the sum with i from 2 to 100 P(100,i) p(n,k)=p(n-1,k-1)+p(n-k,k), start of dinamics with p(i,i)=1, p(i,1)=1, p(i,i+a)=0(a>0)

→ Reply
»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Define F(n,k) to be the number of ways to write n as a sum where the largest number is no more then k. The answer is F(n,n)-1 (remove case when there is only one term in sum).

Recurrence: The recurrence is F(n,k)=F(n,k-1)+F(n-k,k) (when k-1 is largest or use k as a term in the sum and recur).

Base case: For n=0, you can always get n if k>=0. For k=0, the only number you can get is 0.

→ Reply