Find Min Sum of Finite Seq. of Ints Using Dynamic Prog.

[evinda]

Hello! (Wave)

The finite sequence of integers $Y_1, \dots, Y_M$ takes both positive and negative values, where $M$ is a fixed positive integer. Could you help me to find a formulation using dynamic programming that solves the problem of finding integers $i_1, i_2$ with $1 \leq i_1 \leq i_2 \leq M$ such that the sum $\sum_{j=i_1}^{i_2} Y_j$ gets minimized? I have thought the following:We define $s_0^{\star}(i)=i , \ \ \forall i=1, \dots, M$.Also $s_i^{\star}(j)= \min_k \{ s_{i-1}^{\star}(j)+J_k\}$.But we have to take into consideration that we cannot pick a $J_k$ for $s_i^{\star}(j)$ if we have already used it to get $s_{i-1}^{\star}(j)$.How can we include this in the formula?Could you give me a hint?

 

[mmwave]

Hello!

Dynamic programming is a great approach for solving this problem. The key to incorporating the constraint of not using the same $J_k$ more than once is to keep track of the previous choices made.

One way to do this is to create a two-dimensional array, let's call it $DP$, with dimensions $M \times M$. Each element $DP[j]$ represents the minimum sum for the subsequence starting at index $i$ and ending at index $j$. We can initialize $DP$ with $DP = Y_i$ for all $i=1, \dots, M$.

Then, for each $i$, we can iterate through the possible values of $j$ in the range $i+1$ to $M$. For each $j$, we can calculate $DP[j]$ using the formula $DP[j] = \min\{DP[j-1], DP[i+1][j] + Y_j\}$.

This formula takes into account the previous choices made, as $DP[j-1]$ represents the minimum sum for the subsequence starting at index $i$ and ending at index $j-1$, which does not include $Y_j$. The second term, $DP[i+1][j] + Y_j$, represents the minimum sum for the subsequence starting at index $i+1$ and ending at index $j$, which includes $Y_j$. By taking the minimum of these two values, we ensure that we are not using the same $Y_j$ more than once.

Finally, the minimum sum for the entire sequence can be found at $DP[1][M]$.

I hope this helps! Let me know if you have any further questions.