この問題は DP により解くことができます。

花 \(i\) から花 \(j\) までを 1 つの区間としたときの手間を \(f(i,j)\) と表すことにします。

\(\mathrm{DP}[k][i]\) を、\(i\) 番目までの花を \(k\) 個の区間に分割するときの手間の合計の最小値と定めます。

\(i\) 番目の花を含む区間の左端がどこであるかを考えることで、

\(\mathrm{DP}[k][i]=\min_{j\leq i}\left(\mathrm{DP}[k-1][j-1]+f(j,i)\right)\)

となります。この DPは状態数 \(O(NK)\) であり、遷移の計算は愚直に行うと \(O(N^2)\) となるため、全体で \(O(N^3K)\) でこの問題を解くことができます。

\(f(i,j)\) は適切な方法により \(O(N^2)\) で事前計算することもできるので、 \(O(N^2K)\) でこの問題を解くこともできます。

実装例 (C++)

#include<bits/stdc++.h>
using namespace std;
const int INF = 1000000000;

int main(){
  int n, k;
  cin >> n >> k;
  vector<int>a(n);
  for(int i=0; i<n; i++) cin >> a[i];
  
  auto f=[&](int l, int r){
    // [l,r] の max-min  l, r は 1-indexed
    l--;
    int max = *max_element(a.begin() + l, a.begin() + r);
    int min = *min_element(a.begin() + l, a.begin() + r);
    return max - min;
  };
  
  vector<vector<int>>dp(k+1, vector<int>(n+1, INF));
  dp[0][0] = 0;
  for(int kk=1; kk<=k; kk++){
    for(int i=1; i<=n; i++){
      int ans = INF;
      for(int j=1; j<=i; j++){
        ans = min(ans, dp[kk-1][j-1] + f(j, i));
      }
      dp[kk][i] = ans;
    }
  }
  
  cout << dp[k][n] << endl;
}

実装例 (Python)

INF = 10**9

N,K = map(int, input().split())
A = list(map(int, input().split()))

def f(l, r):
  # [l,r] の max-min  l, r は 1-indexed
  l -= 1
  return max(A[l:r]) - min(A[l:r])

dp = [[INF]*(N+1) for _ in range(K+1)]
dp[0][0] = 0
for k in range(1, K+1):
  for i in range(1, N+1):
    dp[k][i] = min(dp[k-1][j-1] + f(j, i) for j in range(1, i+1))

print(dp[K][N])

Bonus： \(O(NK\log N)\) で解いてください（難しめの ABC-F 程度(青後半～黄difficulty程度)の難易度と思われます）

#include<bits/stdc++.h>
#include<atcoder/lazysegtree>
using namespace std;
const int INF = 1000000000;

int xx(int x,int y){return min(x, y);}
int xid(){return INF;}
int fx(int f, int x){return f + x;}
int ff(int f, int g){return f + g;}
int fid(){return 0;}
using SegTree = atcoder::lazy_segtree<int, xx, xid, int, fx, ff, fid>;


int main(){
  int n, k;
  cin >> n >> k;
  // a は 1-index
  vector<int>a(n+1);
  for(int i=1; i<=n; i++) cin >> a[i];
  
  vector<int>dp(n+1, INF);
  dp[0] = 0;
  
  for(int kk=1; kk<=k; kk++){
    SegTree seg(dp);
    vector<array<int,2>>min_stack, max_stack;
    min_stack.push_back({0, 0});
    max_stack.push_back({INF, 0});

  	// seg[j] = dp[kk-1][j] にして、
  	// dp[kk][i] = min(seg[j] + f(j+1, i)) を求めたいので、f部分を差分更新でセグ木をアップデートする
  	// iのループでは、
        // seg[j] = dp[kk-1][j] + f(j+1, i-1) になっているとき、iの影響分を追加する
  	
    for(int i=1;i<=n;i++){
      {  // upd min
        int r = i-1;
        while(min_stack.back()[0] > a[i]){
          auto[v, l] = min_stack.back();
          min_stack.pop_back();
          seg.apply(l, r, v-a[i]);
          r = l;
        }
        min_stack.push_back({a[i], r});
      }
      {  // upd max
        int r = i-1;
        while(max_stack.back()[0] < a[i]){
          auto[v, l] = max_stack.back();
          max_stack.pop_back();
          seg.apply(l, r, a[i]-v);
          r = l;
        }
        max_stack.push_back({a[i], r});
      }
      dp[i] = seg.prod(0,i);
    }
  }
  cout << dp[n] << endl;
}