Planteamiento y alcance
La vara tiene puntos extremos 0 y n, y cuts contiene posiciones internas distintas. En cada paso, elige un corte en el segmento actual, paga la longitud de dicho segmento y divídelo en dos segmentos. Utiliza la escala de LeetCode 1547: n es como máximo 1,000,000 y el número de cortes m es como máximo 100. Devuelve únicamente el costo mínimo; reconstruir un orden requiere almacenar el punto de decisión.
Qué evalúa el entrevistador
- Si reconoces la DP de intervalos en lugar de seguir codiciosamente (greedy) el orden de entrada.
- Si agregas 0 y n como centinelas y ordenas las posiciones de corte.
- Si puedes explicar por qué elegir el primer o último corte divide el problema en intervalos independientes.
- Si puedes enunciar los límites de tiempo, espacio y seguridad de enteros basados en m.
Preguntas de aclaración
- ¿Puede cuts incluir 0, n o duplicados? De ser así, ¿la API debe eliminar duplicados o rechazarlos?
- ¿Necesitamos solo el costo mínimo o también un orden óptimo? Esto último necesita una tabla de decisiones.
- ¿Cuál es el límite superior para m? Un m más grande puede descartar el tiempo cúbico.
- ¿El costo de cada corte es exactamente la longitud del segmento actual? Un costo ponderado cambia la transición.
Respuesta en 30 segundos
Ordeno los cortes y agrego 0 y n. Sea dp[i][j] el costo mínimo para realizar todos los cortes estrictamente entre los puntos i y j; los extremos adyacentes tienen valor cero. Para cada intervalo, pruebo cada pivote interno k como el primer corte. Ese corte cuesta la longitud del intervalo, y los intervalos izquierdo y derecho son independientes, por lo que sumo dp[i][k] y dp[k][j]. Llenar los rangos en orden creciente da dp[0][m+1] en tiempo O(m cubed) y espacio O(m squared).
Respuesta detallada
1. Establecer coordenadas e invariantes
Ordena cuts y construye points con 0, todas las posiciones de corte y n. Después de ordenar, los cortes internos del intervalo desde points[i] hasta points[j] son exactamente los índices entre i y j. Este invariante hace que el estado dependa de los extremos en lugar del historial de cortes anteriores.
2. Definir el estado de intervalo
dp[i][j] es el costo mínimo para realizar todos los cortes estrictamente dentro de points[i] y points[j]. Cuando j es i más uno, no hay corte interno, por lo que el valor es cero. El estado no registra el orden porque, después del primer corte, los subproblemas izquierdo y derecho no interactúan, y cada costo posterior depende únicamente de su segmento actual.
3. Derivar la transición
Si el primer corte es points[k], con i menor que k y k menor que j, el pago actual es points[j] menos points[i]. El corte crea dos intervalos independientes:
dp[i][j] = min(
dp[i][k] + dp[k][j] + points[j] - points[i]
for k in (i + 1 ... j - 1)
)Calcula primero los rangos más cortos para que los valores de ambos subintervalos ya estén disponibles.
4. Implementarlo
function minCost(n: number, cuts: number[]): number {
const points = [0, ...cuts.slice().sort((a, b) => a - b), n];
const m = points.length;
const dp = Array.from({ length: m }, () => Array<number>(m).fill(0));
for (let span = 2; span < m; span += 1) {
for (let left = 0; left + span < m; left += 1) {
const right = left + span;
let best = Number.POSITIVE_INFINITY;
for (let pivot = left + 1; pivot < right; pivot += 1) {
best = Math.min(
best,
dp[left][pivot] + dp[pivot][right] + points[right] - points[left],
);
}
dp[left][right] = best === Number.POSITIVE_INFINITY ? 0 : best;
}
}
return dp[0][m - 1];
}5. Demostrar la transición
Usa inducción sobre el número de cortes internos. Con cero cortes el costo es cero. Asume que los intervalos más cortos son óptimos. Todo ordenamiento óptimo tiene un primer pivote k. Su costo se fija como la longitud total del intervalo; el trabajo restante se divide en los intervalos izquierdo y derecho, cuyos valores óptimos son dp[i][k] y dp[k][j] por inducción. Tomar el mínimo sobre todo k posible cubre cada primer corte, por lo que la transición es óptima.
6. Complejidad, números y reconstrucción
Con m cortes internos hay O(m squared) estados y hasta O(m) pivotes por estado, lo que da un tiempo de O(m cubed) y un espacio de O(m squared). Con n hasta 1,000,000 y m como máximo 100, un number de JavaScript cubre el rango de costos indicado; para costos ponderados mayores, usa BigInt o comprobaciones explícitas de enteros seguros. Para reconstruir un orden, almacena el pivote que logró cada mínimo y emite recursivamente el árbol de decisiones.
7. Contraejemplo y pruebas
Para n=7 y cuts=[1,3,4,5], cortar en el orden de entrada cuesta 20, mientras que el orden 3,5,1,4 cuesta 16. Esto refuta la elección voraz por orden de entrada y de izquierda a derecha. Prueba también un corte, posiciones cerca de los extremos, entrada no ordenada, política de duplicados, brechas consecutivas, m máximo y los intervalos base sin cortes internos.
Respuesta modelo
Ordeno los cortes y agrego 0 y n. dp[i][j] es el costo mínimo para cada corte entre los dos extremos, con cero para extremos adyacentes. Para cada intervalo pruebo el pivote k como el primer corte: pago la longitud del intervalo, luego sumo los costos óptimos izquierdo y derecho. Llenar por rango creciente devuelve el intervalo exterior. Con m cortes la complejidad es de tiempo O(m cubed) y espacio O(m squared); almacenar cada mejor pivote reconstruye un orden. Pruebo con entradas no ordenadas, cortes cercanos a los extremos, un solo corte y el contraejemplo n=7, [1,3,4,5].
Errores comunes
- Cortar en el orden de entrada → Ese orden puede estar lejos de ser óptimo → Ordenar y enumerar el primer pivote con DP de intervalos.
- Omitir 0 y n → Las longitudes de límites y los estados quedan incompletos → Incluir ambos extremos como centinelas.
- Definir dp como el costo de un solo corte → Se omiten los cortes posteriores → Definirlo como el costo mínimo para todo el conjunto interior.
- Elegir el segmento más corto o más largo de forma voraz (greedy) → Las elecciones locales cambian los costos de ambos subproblemas → Mostrar la división recursiva y la prueba de inducción.
- Probar solo entradas ordenadas → El código puede asumir el orden silenciosamente → Copiar y ordenar dentro de la función, luego probar con un arreglo no ordenado.
Preguntas de seguimiento
¿Cómo devuelves un orden de corte óptimo?
Almacena el pivote que logra cada mínimo del intervalo. Emite ese pivote, luego realiza recursión sobre los intervalos izquierdo y derecho. Si varios pivotes empatan, define una regla determinista como el índice más pequeño o el orden lexicográficamente menor.
¿Es aceptable O(m cubed) cuando m crece de 100 a 2,000?
No lo prometas sin realizar mediciones. Estima la cantidad de estados y el presupuesto de tiempo, luego busca estructura adicional, aproximación o restricciones fuera de línea (offline). Una afirmación genérica de O(m squared) requiere una propiedad demostrada de monotonicidad o de desigualdad cuadrangular.
¿Qué pasa si cuts contiene posiciones duplicadas?
Un corte repetido no tiene un segundo efecto físico. Ordena y elimina duplicados, o rechaza duplicados según el contrato de entrada; documenta la elección y pruébala en lugar de crear intervalos de longitud cero.
¿Qué pasa si cada corte cuesta la longitud del segmento multiplicada por un peso?
Si el peso depende solo del pivote k elegido, reemplaza el término de longitud del intervalo con la longitud del intervalo multiplicada por weight[k], y la división permanece independiente. Si el costo depende del historial, el recuento de cortes o el estado entre intervalos, los subproblemas ya no son independientes y el estado debe rediseñarse.