1246. Palindrome Removal

LeetCode hard original: C# #array #csharp #dynamic-programming #hard #leetcode #math #recursion #string

El texto de la tarea se traduce del ruso para el idioma seleccionado. El código no cambia.

LeetCode Static

Вам дан entero arreglo arr. За один ход вы можете выбрать палиндромный подarreglo arr[i], arr[i + 1], ..., arr[j], где i <= j, и удалить этот подarreglo из данного arregloа. Обратите внимание, что после удаления подarregloа elementы слева и справа от него перемещаются, чтобы заполнить пробел, образовавшийся в результате удаления. return минимальное количество ходов, необходимое для удаления всех чисел из arregloа.

Ejemplo:

Input: arr = [1,2]

Output: 2

C# solución

coincidente/original

using System;
public class Solution {
    public int MinMovesToDelete(int[] arr) {
        int n = arr.Length;
        int[,] dp = new int[n, n];
        for (int i = 0; i < n; i++) {
            dp[i, i] = 1;
        }
        for (int length = 2; length <= n; length++) {
            for (int i = 0; i <= n - length; i++) {
                int j = i + length - 1;
                if (arr[i] == arr[j]) {
                    dp[i, j] = length > 2 ? dp[i + 1, j - 1] : 1;
                } else {
                    dp[i, j] = int.MaxValue;
                    for (int k = i; k < j; k++) {
                        dp[i, j] = Math.Min(dp[i, j], dp[i, k] + dp[k + 1, j]);
                    }
                }
            }
        }
        return dp[0, n - 1];
    }
}

C++ solución

borrador automático, revisar antes de enviar

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int MinMovesToDelete(vector<int>& arr) {
        int n = arr.size();
        int[,] dp = new int[n, n];
        for (int i = 0; i < n; i++) {
            dp[i, i] = 1;
        }
        for (int length = 2; length <= n; length++) {
            for (int i = 0; i <= n - length; i++) {
                int j = i + length - 1;
                if (arr[i] == arr[j]) {
                    dp[i, j] = length > 2 ? dp[i + 1, j - 1] : 1;
                } else {
                    dp[i, j] = int.MaxValue;
                    for (int k = i; k < j; k++) {
                        dp[i, j] = min(dp[i, j], dp[i, k] + dp[k + 1, j]);
                    }
                }
            }
        }
        return dp[0, n - 1];
    }
}

Java solución

coincidente/original

public class Solution {
    public int minMovesToDelete(int[] arr) {
        int n = arr.length;
        int[][] dp = new int[n][n];

        for (int i = 0; i < n; i++) {
            dp[i][i] = 1;
        }

        for (int length = 2; length <= n; length++) {
            for (int i = 0; i <= n - length; i++) {
                int j = i + length - 1;
                if (arr[i] == arr[j]) {
                    dp[i][j] = length > 2 ? dp[i + 1][j - 1] : 1;
                } else {
                    dp[i][j] = Integer.MAX_VALUE;
                    for (int k = i; k < j; k++) {
                        dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j]);
                    }
                }
            }
        }

        return dp[0][n - 1];
    }
}

JavaScript solución

coincidente/original

var minMovesToDelete = function(arr) {
    const n = arr.length;
    const dp = Array.from({ length: n }, () => Array(n).fill(0));

    for (let i = 0; i < n; i++) {
        dp[i][i] = 1;
    }

    for (let length = 2; length <= n; length++) {
        for (let i = 0; i <= n - length; i++) {
            const j = i + length - 1;
            if (arr[i] === arr[j]) {
                dp[i][j] = length > 2 ? dp[i + 1][j - 1] : 1;
            } else {
                dp[i][j] = Infinity;
                for (let k = i; k < j; k++) {
                    dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j]);
                }
            }
        }
    }

    return dp[0][n - 1];
};

Python solución

coincidente/original

def min_moves_to_delete(arr):
    n = len(arr)
    dp = [[0] * n for _ in range(n)]

    for i in range(n):
        dp[i][i] = 1

    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if arr[i] == arr[j]:
                dp[i][j] = dp[i + 1][j - 1] if length > 2 else 1
            else:
                dp[i][j] = float('inf')
                for k in range(i, j):
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j])

    return dp[0][n - 1]

Go solución

coincidente/original

package main

import (
    "fmt"
    "math"
)

func minMovesToDelete(arr []int) int {
    n := len(arr)
    dp := make([][]int, n)
    for i := range dp {
        dp[i] = make([]int, n)
        dp[i][i] = 1
    }

    for length := 2; length <= n; length++ {
        for i := 0; i <= n-length; i++ {
            j := i + length - 1
            if arr[i] == arr[j] {
                if length > 2 {
                    dp[i][j] = dp[i+1][j-1]
                } else {
                    dp[i][j] = 1
                }
            } else {
                dp[i][j] = math.MaxInt32
                for k := i; k < j; k++ {
                    dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j])
                }
            }
        }
    }
    return dp[0][n-1]
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

Algorithm

1⃣Базовый случай:

Если подarreglo состоит из одного elementа, то его удаление займет 1 ход, поэтому dp[i][i] = 1.

2⃣Рекурсивный случай:

Если arr[i] == arr[j], то мы можем удалить их в одном ходе, если подarreglo arr[i+1...j-1] можно удалить за dp[i+1][j-1] ходов, тогда dp[i][j] = dp[i+1][j-1] (если удалим подarreglo arr[i+1...j-1] и затем удалим arr[i] и arr[j]).

3⃣В противном случае, минимальное количество ходов для удаления подarregloа arr[i...j] будет равно 1 + минимум ходов для удаления каждого из подarregloов arr[i...k] и arr[k+1...j], где i <= k < j. То есть, dp[i][j] = min(dp[i][k] + dp[k+1][j]) для всех k от i до j-1.

😎

Vacantes para esta tarea

Se muestran vacantes activas con etiquetas coincidentes.

Todas las vacantes

Todavía no hay vacantes activas.