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.
Hint: state (pos,cnt) pos:in which state you are: cnt: whats the postion of this state in the taken subsequence.
Thanks. The problem has been solved with the help of VladHaivas0205 and you.
Can you help me with this problem?
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 VladHaivas0205.