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

Stuck in a DP problem
Автор skpro19, история, 7 лет назад, По-английски

The question is this.

The solution is something like this:

dp[1] = 1, dp[2] =3 ;

for(int i =3; i <= n ; i++) dp[i] = dp[i — 1] + dp[ i- 2] + 2;

How did one come with the formulation dp[i] = dp[ i — 1 ] + dp[i — 2] + 2 ?

Any help would be really appreciated.

Peace!

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

»
7 лет назад, # |
← Rev. 7   Проголосовать: нравится +2 Проголосовать: не нравится

Its a result of this simple calculation... - we can write dp[i] as all the ways to select such that ith one is selected. So now we have

  • dp[i]=dp[i-1]+dp[i-3]+dp[i-5]....1 using the same rule we can write...2

  • dp[i-1]=dp[i-2]+dp[i-4]+....3 on adding these two... we see that

  • Result:dp[i]+dp[i-1]=dp[i-1]+dp[i-2]+dp[i-3]+...(all the ters upto 1). now dp[i] in eq 1 can also be written as

  • dp[i]=1+(1+dp[i-2]+dp[i-4]+.....)+dp[i-3]+dp[i-4]... which is dp[i]=2+dp[i-1]+dp[i-2]...from the above result.

  • I guess this proof suffices... you can also derive this by directly taking prefix sum in DP but this i guess is more understandable.

  • The one is added because we are not considering single element in all the previous DP's

→ Ответить