Lighting the street solution

#include <iostream>
using namespace std;

int m, k, a[55], dp[55][55];

int sol(int l, int r)
{
	if((l + 1) == r) return 0;
	if(dp[l][r] != 1e6) return dp[l][r];
	int ans = 1e6;
	for(int i = l + 1; i < r; ++i)
		ans = min(ans, sol(l, i) + sol(i, r) + a[r] - a[l]);
	return dp[l][r] = ans;
}

int main() {
	int n;
	cin >> n;
	while(n--)
	{
		cin >> m >> k;
		a[0] = 0, a[k + 1] = m;
		for(int i = 1; i <= k; ++i) cin >> a[i];
		for(int i = 0; i <= (k + 1);++i)
		    for(int j = 0; j <= (k + 1);++j)
		        dp[i][j] = 1e6;
		cout << sol(0, k + 1) << endl;
	}
	return 0;
}