title: Not getting the approach in a minimization algorithm
body: <p>Recently, I was trying to solve this <a href="http://codeforces.com/problemset/problem/868/F" rel="nofollow noreferrer">dynamic programing problem</a>, but somehow not getting the approach to solve it. </p>
  
  <p>The editorial to the problem seems very confusing too and i would understand how to think properly to approach this problem. </p>
  
  <p>Thanks.</p>
  
  <h2>The problem</h2>
  
  <p><strong>F. Yet Another Minimization Problem</strong>: Time limit per test: 2 seconds |
  Memory limit per test: 256 megabytes |
  Input: standard input |
  Output: standard output</p>
  
  <p>You are given an array of n integers <code>a1... an</code>. The cost of a subsegment is the number of unordered pairs of distinct indices within the subsegment that contain equal elements. Split the given array into <code>k</code> non-intersecting non-empty subsegments so that the sum of their costs is minimum possible. Each element should be present in exactly one subsegment.</p>
  
  <p><strong>Input</strong></p>
  
  <p>The first line contains two integers <code>n</code> and <code>k (2 ≤ n ≤ 105, 2 ≤ k ≤ min (n, 20))</code> - the length of the array and the number of segments you need to split the array into.</p>
  
  <p>The next line contains <code>n</code> integers <code>a1, a2, ..., an (1 ≤ ai ≤ n)</code> - the elements of the array.</p>
  
  <p><strong>Output</strong></p>
  
  <p>Print single integer: the minimum possible total cost of resulting subsegments.</p>
  
  <p><strong>Example 1</strong></p>
  
  <pre><code>input
  7 3
  1 1 3 3 3 2 1
  output
  1
  </code></pre>
  
  <p><strong>Example 2</strong></p>
  
  <pre><code>input
  10 2
  1 2 1 2 1 2 1 2 1 2
  output
  8
  </code></pre>
  
  <p><strong>Example 3</strong></p>
  
  <pre><code>input
  13 3
  1 2 2 2 1 2 1 1 1 2 2 1 1
  output
  9
  </code></pre>
  
  <p><strong>Note:</strong> </p>
  
  <p>In the first example it's optimal to split the sequence into the following three subsegments: <code>[1], [1, 3], [3, 3, 2, 1]</code>. The costs are <code>0, 0</code> and <code>1</code>, thus the answer is 1.</p>
  
  <p>In the second example it's optimal to split the sequence in two equal halves. The cost for each half is <code>4</code>.</p>
  
  <p>In the third example it's optimal to split the sequence in the following way: <code>[1, 2, 2, 2, 1], [2, 1, 1, 1, 2], [2, 1, 1]</code>. The costs are <code>4, 4, 1</code>.</p>