Sea a[i] la posicion del i-esimo corte en la cadena y ademas sean a[0] = 0 
y a[m+1] = n para indicar dos cortes artificiales en los extremos de la 
cadena (esto no es necesario, pero facilita muchisimo la codificacion).

Por otro lado, sea f[i][j] el costo minimo de cortar el segmento de la 
cadena a[i] a a[j] por lo que f[i][j] = 0 si i = j o si i+1 = j, mientras 
que f[i][j] = (a[j] - a[i]) + min {f[i][k] + f[k][j]} cuando se cumpla que 
i+1 <= j-1 donde el minimo se toma con i < k < j. El valor buscado sera 
f[0][m+1] al final del programa. Note que para calcular f[i][j] se deben 
calcular primero f[i][k] y f[k][j] para toda i < k < j, por lo que la i 
debe moverse de mayor a menor y la j debe moverse de menor a mayor. (NOTA: 
por supuesto que habia una mejor forma de resolver el ejemplo descrito en 
el enunciado de la tarea). Observe que el calculo de la matriz f[][] se 
hace con tres ciclos, de modo que el tiempo que se tarda es proporcional 
al cubo de M (y no tiene nada que ver con N).

#include <stdio.h>

int main(void)
{
  int i, j, k, m, n, s, t;
  int a[1002];
  int f[1002][1002];

  scanf("%d%d", &n, &m);

  a[0] = 0; a[m+1] = n;
  for (i = 1; i <= m; i++)
    scanf("%d", &a[i]);

  for (i = m+1; i >= 0; i--)
    for (j = i; j <= m+1; j++) {
      if (i == j || i+1 == j)
	f[i][j] = 0;
      else {
	t = f[i][i+1] + f[i+1][j];
	for (k = i+2; k < j; k++)
	  if ((s = f[i][k] + f[k][j]) < t)
	    t = s;
	f[i][j] = a[j] - a[i] + t;
      }
    }

  printf("%d\n", f[0][m+1]);
  return 0;
}