Блог пользователя ialwaysusethisaccount

how to do project euler 76 with DP
Автор ialwaysusethisaccount, 9 лет назад, По-английски

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.

  • Проголосовать: нравится
  • -2
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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)

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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.

→ Ответить