By AdHocMan, history, 11 months ago,

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.

• +13

 » 11 months ago, # |   +6 Hint: state (pos,cnt) pos:in which state you are: cnt: whats the postion of this state in the taken subsequence.
•  » » 11 months ago, # ^ |   +6 Thanks. The problem has been solved with the help of VELJAODI and you.
 » 11 months ago, # |   0 Can you help me with this problem?
•  » » 11 months ago, # ^ |   +6 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 .. nfor j 0..iif(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 VELJAODI.