How to approach this DP problem.

Revision en1, by Hd7, 2019-08-19 18:24:39

Hi Codeforces Community, I have just solved this problem.
Link problems
Even though I solved it by myself, i still feel i'm missing anything, i feel uncomfortable.
The problem requires we find out k ranges (size = m) in the way that sum of all elements in every ranges is maximal. I came up with the ideal that:
$$$f(i,j)$$$ is the maximum sum of all elements in j range (size = m) when we have already gone to a[i]. So

$$$f(i,j) = max(f(i-1,j), f(i-m, j-1) + \sum_{x=i-m+1}^{i} a_x)$$$

The answer will be $$$f(n,k)$$$.
I still feel like i don't understand it absolutely. As usual, i try to form my DP problem to a graph and find the shortest (or longest) path depended on statement.
I want to ask the way you approach for a DP problem.
Thanks in advance, i am studying dynamic programming.

Tags #dp

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Hd7 2019-08-19 18:24:39 892 Initial revision (published)