AdHocMan's blog

Help needed in a DP problem.
By AdHocMan, history, 3 years ago, In English

As I am very new to dynamic programming I am facing many problems in understanding the states of the DP. Here is a problem which I have tried to solve by iterative method but failed. Can anyone please help me with this problem by giving me a bit description on how to understand the states of this type of problems?

Problem Statement: Find a sub-sequence $$$(a_{b1}, a_{b2}, a_{b3},\dots)$$$ of array $$$a$$$ of size $$$n(n < 1001)$$$ to maximize the following expression: $$$1*a_{b1} + 2*a_{b2} + 3*a_{b3} + \dots$$$. Print the maximum value of the expression.

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

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

Hint: state (pos,cnt) pos:in which state you are: cnt: whats the postion of this state in the taken subsequence.

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

Can you help me with this problem?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    At first initialize every element in $$$dp$$$ with $$$-INF$$$ (to be sure you don't access something you don't want to). Except $$$dp[0][0]$$$ which should be $$$0$$$.

    For each element you decide if you select it or not so $$$dp[i][j] = max(dp[i - 1][j]$$$ (don't select it), $$$dp[i - 1][j - 1] + a[i] * j$$$(or select it)).

    for i 1 .. n

    for j 0..i

    if(j > i - 1) forget about $$$dp[i - 1][j]$$$ (don't select it) (you can't select $$$j$$$ elements from $$$i - 1$$$)

    if(j == 0) forget about $$$dp[i - 1][j - 1] + a[i] * j$$$ (you can't select $$$0$$$ if you selected $$$a[i]$$$)

    This was the approach what I got from VladHaivas0205.

    → Reply