### Hd7's blog

By Hd7, history, 10 months ago, ,

Hi Codeforces Community, I have just solved this problem.
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.

• 0

 » 10 months ago, # |   0 I think the easiest way to understand dp problem is to imagine brute force solution. After that, u can see, which things happens many times (we calculate the same thing lots of times) (It calls "Recursion tree") Then, u can easy remember the value, which u got after first calculation (it calls "Memoisation") So solution is: write brute force solution + add memoisation -> PROFIT :)what i am talking about: 59102892
•  » » 10 months ago, # ^ |   0 Brute force for problems like that is not easy (for me). Thanks for your reply